Five-color version of the planar equitable coloring theorem
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.