Cranston's sparse-graph odd coloring conjecture

About 4 years old · traced to

Let GG be a finite simple graph, let c≥4c\geq 4, and let mad⁡(G)\operatorname{mad}(G) be its maximum average degree, defined by

mad⁡(G)=max⁡∅≠H⊆G{2∣E(H)∣∣V(H)∣}.\operatorname{mad}(G)=\max_{\emptyset\neq H\subseteq G}\left\{\frac{2|E(H)|}{|V(H)|}\right\}.

An odd cc-coloring is a proper cc-coloring in which every non-isolated vertex has a color appearing an odd number of times in its open neighborhood, and let χo(G)\chi_o(G) denote the minimum cc for which GG has an odd cc-coloring. Cranston's conjecture. If

mad⁡(G)<4cc+2,\operatorname{mad}(G)<\frac{4c}{c+2},

then χo(G)≤c\chi_o(G)\leq c. The conjecture is known to hold for c∈{5,6}c\in\{5,6\}, while the c=4c=4 formulation is false: a graph whose every block is a 55-cycle is a counterexample.

References

Primary source

Tao Wang and Xiaojing Yang, “On odd colorings of sparse graphs”, arXiv:2212.06563 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.