Equitable coloring conjecture for outerplanar graphs with four or five colors
Equitable coloring conjecture for outerplanar graphs with four or five colors
Let be an outerplanar graph, let or , and for each vertex let denote the maximum size of an independent set containing . An equitable -coloring is a proper coloring with color classes whose sizes differ by at most one.
Equitable coloring conjecture. If
then has an equitable -coloring.
The condition is necessary for an equitable -coloring, and the conjecture would extend the corresponding theorem for trees to all outerplanar graphs. It is known for , while the cases and remain open; the paper gives modest support by showing that the case implies the case .
Sources & referencesView supporting material
Primary source
Daniel W. Cranston and Reem Mahmoud, “Equitably Coloring Planar and Outerplanar Graphs”, arXiv:2509.16123 (2025).
Additional references
3 papers in this index state this conjecture (2010–2025). The statement above is taken from the most recent of them; the others are arXiv:1307.4803, arXiv:1005.4079.
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.