Equitable coloring of planar graphs with maximum degree at least eight

Alexandr Kostochka, Duo Lin, Zimu Xiang

Research output: Contribution to journalArticlepeer-review


The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ≥3 that is not the complete graph KΔ+1 or the complete bipartite graph KΔ,Δ admits an equitable coloring with Δ colors. For planar graphs, the conjecture has been confirmed for Δ≥13 by Yap and Zhang and for 9≤Δ≤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 Δ≥9 and for planar graphs with maximum degree Δ≥8.

Original languageEnglish (US)
Article number113964
JournalDiscrete Mathematics
Issue number6
StatePublished - Jun 2024


  • Equitable coloring
  • Planar graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Equitable coloring of planar graphs with maximum degree at least eight'. Together they form a unique fingerprint.

Cite this