2025/09/19 by Daniel W. Cranston, Cranston, Daniel W., Reem Mahmoud +1
Computer Science · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2509.16123
openalex publication_date 2025/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A proper s-coloring of an n-vertex graph is equitable if every color class has size \lfloorn/s\rfloor or \lceiln/s\rceil. A necessary condition to have an equitable s-coloring is that every vertex v appears in an independent set of size at least \lfloorn/s\rfloor. That is minv∈ V(G)αv≥ \lfloorn/s\rfloor. Various authors showed that when G is a tree and s≥ 3 this obvious necessary condition is also sufficient. Kierstead, Kostochka, and Xiang asked whether this result holds more generally for all outerplanar graphs. We show that the answer is No when s=3, but that the answer is Yes when s≥ 6. The case s∈\4,5\ remains open. We also prove an analogous result for planar graphs, with a necessary and sufficient hypothesis. Fix s≥ 40. Let G be a planar graph, and let w0,w1 be its 2 vertices with largest degrees. If there exist disjoint independent sets I0, I1 such that |I0|=\lfloorn/s\rfloor and |I1| = \lfloor(n+1)/s\rfloor and w0,w1∈ I0∪ I1, then G has an equitable s-coloring.