On odd colorings of sparse graphs.

An 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 within its open neighborhood. A proper conflict-free c - coloring of a graph is a proper c -coloring such that each non-isolated vertex has a color appearing exactly once within its neighborhood. Clearly, every proper conflict-free c -coloring is also an odd c -coloring. Cranston conjectured that every graph G with maximum average degree mad (G) < 4 c c + 2 (where c ≥ 4) has an odd c -coloring, and he proved this conjecture for c ∈ { 5 , 6 }. Note that the bound 4 c c + 2 is best possible. Cho et al. solved Cranston's conjecture for c ≥ 5 , strengthening the result by transitioning from odd c -coloring to proper conflict-free c -coloring. However, they did not provide all the extremal non-colorable graphs G with mad (G) = 4 c c + 2 , which remains an open question of interest. In this paper, we tackle this intriguing extremal problem. We aim to characterize all non-proper conflict-free c -colorable graphs G with mad (G) = 4 c c + 2 . For the case of c = 4 , Cranston's conjecture is not true, as evidenced by the existence of a counterexample: a graph whose every block is a 5-cycle. Cho et al. proved that a graph G with mad (G) < 22 9 and no induced 5-cycles has an odd 4-coloring. We improve this result by proving that a graph G with mad (G) ≤ 22 9 (with equality allowed) is not odd 4-colorable if and only if G belongs to a specific class of graphs. On the other hand, Cho et al. established that a planar graph with girth at least 5 has an odd 6-coloring; we improve it by proving that a planar graph without 4 − -cycles adjacent to 7 − -cycles also has an odd 6-coloring. [ABSTRACT FROM AUTHOR]