Cranston's maximum-average-degree conjecture for odd colorings

Let GG be a finite simple graph, let mad(G)\operatorname{mad}(G) be the maximum of 2E(H)V(H)\frac{2|E(H)|}{|V(H)|} over all non-empty subgraphs HH of GG, and let χo(G)\chi_o(G) be the least positive integer cc for which GG has a proper cc-coloring in which every vertex of positive degree has some color appearing an odd number of times among its neighbors. Cranston's conjecture. For c4c\geq 4, if

mad(G)4c4c+1,\operatorname{mad}(G)\leq\frac{4c-4}{c+1},

then χo(G)c\chi_o(G)\leq c. Cranston proved this conjecture for c{5,6}c\in\{5,6\}, while the cases c4c\geq 4 in general remain open. It gives a sharp-looking sparsity threshold guaranteeing an odd coloring.

Sources & referencesView supporting material

Primary source

Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon and Boram Park, “Odd coloring of sparse graphs and planar graphs”, arXiv:2202.11267 (2022).

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.