Improved bounds for some facially constrained colorings

Štorgel, Kenny 

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 151-158

Résumé

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. 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. Czap and Jendroľ in [Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703], conjectured that 10 colors suffice in both colorings. We present an infinite family of counterexamples to both conjectures. A facial (P_k, P_𝓁 )-WORM coloring of a plane graph G is a vertex-coloring such that G contains neither rainbow facial k-path nor monochromatic facial 𝓁-path. Czap, Jendroľ and Valiska in [WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017) 353–368], proved that for any integer n≥ 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. They also asked whether there exists a graph with maximum degree 4 having the same property. We prove that for any integer n≥ 18, there exists a connected plane graph, with maximum degree 4, with no facial (P_3,P_3)-WORM coloring.

Détail

Keywords: plane graph, facial coloring, facial-parity edge-coloring, facial-parity vertex-coloring, WORM coloring