Five-color version of the planar equitable coloring theorem

About 1 year old · traced to

Let GG be a planar graph, and let w0,w1w_0,w_1 be its two vertices with largest degrees, breaking ties arbitrarily. Let s≥40s\ge 40. If there exist disjoint independent sets I0,I1I_0,I_1 such that

∣I0∣=⌊ns⌋,∣I1∣=⌊n+1s⌋,|I_0|=\left\lfloor\frac{n}{s}\right\rfloor, \qquad |I_1|=\left\lfloor\frac{n+1}{s}\right\rfloor,

and w0,w1∈I0∪I1w_0,w_1\in I_0\cup I_1, then GG has an equitable ss-coloring.

Five-color planar theorem conjecture. The same statement remains true when the lower bound s≥40s\ge 40 is replaced by s≥5s\ge 5.

The paper proves the planar theorem for s≥40s\ge 40 and conjectures that the threshold can be reduced to 55. 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

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.