Five-color version of the planar equitable coloring theorem
Let be a planar graph, and let be its two vertices with largest degrees, breaking ties arbitrarily. Let . If there exist disjoint independent sets such that
and , then has an equitable -coloring.
Five-color planar theorem conjecture. The same statement remains true when the lower bound is replaced by .
The paper proves the planar theorem for and conjectures that the threshold can be reduced to . The conjecture concerns strengthening the sufficient condition for equitable colorability of planar graphs; the authors note that they have not optimized the proved bound and believe it is far from best possible.
References
Primary source
Daniel W. Cranston and Reem Mahmoud, “Equitably Coloring Planar and Outerplanar Graphs”, arXiv:2509.16123 (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
No solutions have been posted yet.