Improved bounds for some facially constrained colorings (Q2107748)

In this paper, the author deals with families of graphs for three different and related chromatic problems in planar graphs. First, a facial-parity edge-coloring of a 2-edge-connected plane graph is a facially-proper edge-coloring in which every face is incident with zero or an odd number of edges of each color. Some authors conjectured that 10 colors suffice in this coloring. In this paper, an infinite family of counterexamples that need 12 colors is presented. The best-known upper bound so far is 16 colors. Second, a facial-parity vertex-coloring of a 2-connected plane graph is a proper vertex-coloring in which every face is incident with zero or an odd number of vertices of each color. Some authors conjectured that 10 colors suffice in this coloring. In this paper, an infinite family of counterexamples that needs 12 colors is presented. The best-known upper bound so far is 97 colors. Third, a facial \((P_k,P_l)\)-WORM coloring of a plane graph \(G\) is a vertex-coloring such that \(G\) contains neither a heterochromatic facial \(k\)-path nor a monochromatic facial \(l\)-path. Some authors proved that for any integer \(n\geq 12\) there exists a connected plane graph on \(n\) vertices, with maximum degree at least \(6\), having no facial \((P_3 , P_3 )\)-WORM coloring, and also asked whether there exists a graph with maximum degree \(4\) having the same property. In this paper, it is proved that for any integer \(n\geq 18\), there exists a connected plane graph, with maximum degree \(4\), with no facial \((P_3,P_3)\)-WORM coloring.