Improved bounds for some facially constrained colorings

DOI10.7151/DMGT.2357zbMATH Open1506.05078arXiv2005.09979OpenAlexW3102720887MaRDI QIDQ2107748FDOQ2107748

Authors: Kenny Štorgel 

Publication date: 2 December 2022

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

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.

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

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

zbMATH Keywords

plane graphfacial coloringWORM coloringfacial-parity edge-coloringfacial-parity vertex-coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)