A refinement of a result of Corrádi and Hajnal

H. A. Kierstead, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review


Corrádi and Hajnal proved that for every k ≥ 1 and n ≥ 3k, every n-vertex graph with minimum degree at least 2k contains k vertex-disjoint cycles. This implies that every 3k-vertex graph with maximum degree at most k − 1 has an equitable k-coloring. We prove that for s∈{3,4} if an sk-vertex graph G with maximum degree at most k has no equitable k-coloring, then G either contains Kk+1 or k is odd and G contains Kk,k. This refines the above corollary of the Corrádi-Hajnal Theorem and also is a step toward the conjecture by Chen, Lih, and Wu that for r ≥ 3, the only connected graphs with maximum degree at most r that are not equitably r-colorable are Kr,r (for odd r) and Kr+1.

Original languageEnglish (US)
Pages (from-to)497-512
Number of pages16
Issue number4
StatePublished - Aug 22 2015


  • 05C15
  • 05C35

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'A refinement of a result of Corrádi and Hajnal'. Together they form a unique fingerprint.

Cite this