Equitable coloring conjecture for outerplanar graphs with four or five colors

Let GG be an outerplanar graph, let sobreak be 4s obreak\text{ be }4 or 55, and for each vertex vv let b1v(G)b1_v(G) denote the maximum size of an independent set containing vv. An equitable ss-coloring is a proper coloring with ss color classes whose sizes differ by at most one.

Equitable coloring conjecture. If

minvV(G)αv(G)Gs,\min_{v\in V(G)}\alpha_v(G)\ge \left\lfloor\frac{|G|}{s}\right\rfloor,

then GG has an equitable ss-coloring.

The condition is necessary for an equitable ss-coloring, and the conjecture would extend the corresponding theorem for trees to all outerplanar graphs. It is known for s6s\ge 6, while the cases s=4s=4 and s=5s=5 remain open; the paper gives modest support by showing that the case s=4s=4 implies the case s=5s=5.

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

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.