Cranston's sparse-graph odd coloring conjecture
Cranston's sparse-graph odd coloring conjecture
Let be a finite simple graph, let , and let be its maximum average degree, defined by
An odd -coloring is a proper -coloring in which every non-isolated vertex has a color appearing an odd number of times in its open neighborhood, and let denote the minimum for which has an odd -coloring. Cranston's conjecture. If
then . The conjecture is known to hold for , while the formulation is false: a graph whose every block is a -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.