Answers are grounded in this paper and cite their sources.
Research uncovers limits of equitable coloring for outerplanar graphs, indicating key thresholds based on vertex degrees.
A proper s-coloring of an n-vertex graph is equitable if every color class has size n/s or n/s. A necessary condition to have an equitable s-coloring is that every vertex v appears in an independent set of size at least n/s. That is minv∈ V(G)αᵥ≥ n/s. 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 w₀,w₁ be its $2$ vertices with largest degrees. If there exist disjoint independent sets I₀, I₁ such that |I₀|=n/s and |I₁| = (n+1)/s and w₀,w₁∈ I₀∪ I₁, then G has an equitable s-coloring.
No takes yet. Share an insight, caveat, or question.
Cranston et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: