Equitable coloring of planar graphs with maximum degree at least eight

Abstract

The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree $\Delta \ge 3$ that is not the complete graph $K_{\Delta +1}$ or the complete bipartite graph $K_{\Delta ,\Delta }$ admits an equitable coloring with $\Delta$ colors. For planar graphs, the conjecture has been confirmed for $\Delta \ge 13$ by Yap and Zhang and for $9\le \Delta \le 12$ by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree $\Delta \ge 9$ and for planar graphs with maximum degree $\Delta \ge 8$.

19 pages, 3 figures