Improved bounds for some facially constrained colorings

DOI10.7151/DMGT.2357MaRDI QIDQ2107748zbMATH OpenOpenAlexFDO

Authors Kenny Štorgel

Publication date 2 December 2022

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/2005.09979

zbMATH Keywords

facial coloringfacial-parity edge-coloringfacial-parity vertex-coloringplane graphWORM coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 facially-proper vertex-coloring in which every face is incident with zero or an odd number of vertices of each color. Czap and Jendrov{l} (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_{ell})$-WORM coloring of a plane graph $G$ is a coloring of the vertices such that $G$ contains no rainbow facial $k$-path and no monochromatic facial $ell$-path. Czap, Jendrov{l} and Valiska (in WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017), 353--368), proved that for any integer $nge12$ 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 if there exists a graph with maximum degree $4$ having the same property. We prove that for any integer $nge18$, there exists a connected plane graph, with maximum degree $4$, with no facial $(P_3,P_3)$-WORM coloring.

Review text

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.

Recommendations

• Improved bound on facial parity edge coloring
• New bounds for facial nonrepetitive colouring
• On improving the edge-face coloring theorem
• Facially-constrained colorings of plane graphs: a survey
• Improved bounds on coloring of graphs
• Maximum face-constrained coloring of plane graphs
• Improved bounds on acyclic edge colouring
• Improved bounds for weak coloring numbers
• Colouring vertices of plane graphs under restrictions given by faces
• A counterexample to a conjecture on facial unique-maximal colorings

Cites work

• 3-consecutive C-colorings of graphs
• \(F\)-WORM colorings: results for 2-connected graphs
• An improved bound on parity vertex colourings of outerplane graphs
• Colorings of plane graphs without long monochromatic facial paths
• Facial parity edge coloring of outerplane graphs
• Facial parity edge colouring
• Facial parity edge colouring of plane pseudographs
• Facially-constrained colorings of plane graphs: a survey
• Graph colorings with local constraints -- a survey
• Improved bound on facial parity edge coloring
• Parity vertex coloring of outerplane graphs
• Parity vertex colouring of plane graphs
• Strong parity vertex coloring of plane graphs
• Vertex coloring without large polychromatic stars
• Worm colorings
• WORM colorings forbidding cycles or cliques
• WORM colorings of planar graphs

Cited in

(4)

• A survey on the cyclic coloring and its relaxations
• Facial parity edge colouring of plane pseudographs
• Facet-generating procedures for the maximum-impact coloring polytope
• On strong odd colorings of graphs

This page was built for publication: Improved bounds for some facially constrained colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107748)