Odd coloring of sparse graphs and planar graphs

DOI10.1016/J.DISC.2022.113305MaRDI QIDQ6391902arXivFDO

Authors Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon, Boram Park

Publication date 22 February 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.113305

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

arXiv classification

math.CO

Abstract: An {it odd $c$-coloring} of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing an odd number of times on its neighborhood. This concept was introduced very recently by Petruv sevski and v Skrekovski and has attracted considerable attention. Cranston investigated odd colorings of graphs with bounded maximum average degree, and conjectured that every graph $G$ with $mad(G)leqfrac4c-4c+1$ has an odd $c$-coloring for $cgeq4$, and proved the conjecture for $cin5,6$. In particular, planar graphs with girth at least $7$ and $6$ have an odd $5$-coloring and an odd $6$-coloring, respectively. We completely resolve Cranston's conjecture. For $cgeq7$, we show that the conjecture is true, in a stronger form that was implicitly suggested by Cranston, but for $c=4$, we construct counterexamples, which all contain $5$-cycles. On the other hand, we show that a graph $G$ with $mad(G)<frac229$ and no induced $5$-cycles has an odd $4$-coloring. This implies that a planar graph with girth at least 11 has an odd $4$-coloring. We also prove that a planar graph with girth at least 5 has an odd $6$-coloring.

This page was built for publication: Odd coloring of sparse graphs and planar graphs

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