Cranston's sparse-graph odd coloring conjecture

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

mad(G)=maxHG{2E(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.

Sources & referencesView supporting material

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.