Five-color version of the planar equitable coloring theorem

Let GG be a planar graph, and let w0,w1w_0,w_1 be its two vertices with largest degrees, breaking ties arbitrarily. Let s40s\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,w1I0I1w_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 s40s\ge 40 is replaced by s5s\ge 5.

The paper proves the planar theorem for s40s\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.

Sources & referencesView supporting material

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.