Facial edge–face coloring of K4-minor-free graphs

Abstract Let G be a plane graph. Two edges are said to be facially adjacent if they are consecutive on the boundary walk of a face of G . We call G facially edge–face k -colorable if there is a mapping from E ( G ) ∪ F ( G ) to a k color set so that any two facially adjacent edges, adjacent faces, and incident edge and face receive distinct colors. The facial edge–face chromatic number of G , denoted by χ e f ( G ) , is defined to be the least integer k such that G is facially edge–face k -colorable. In 2016, Fabrici, Jendrol’ and Vrbjarova conjectured that every connected, loopless, bridgeless plane graph is facially edge–face 5-colorable. In this paper, we confirm this conjecture for the case of K 4 -minor-free graphs. More precisely, we prove that every bridgeless K 4 -minor-free graph is facially edge–face 5-colorable. Moreover, the upper bound 5 is best possible.