Graphs with chromatic number close to maximum degree

Alexandr V. Kostochka, Landon Rabern, Michael Stiebitz

Research output: Contribution to journalArticlepeer-review


Let G be a color-critical graph with χ(G)<Δ(G)=2t+1<5 such that the subgraph of G induced by the vertices of degree 2t+1 has clique number at most t-1. We prove that then either t<3 and G=K2 t+2 or t=2 and G∈ K6, O5, where O5 is a special graph with χ( O5)=5 and | O5|=9. This result for t<3 improves a case of a theorem by Rabern (2012) [9] and for t=2 answers a question raised by Kierstead and Kostochka (2009) in [6].

Original languageEnglish (US)
Pages (from-to)1273-1281
Number of pages9
JournalDiscrete Mathematics
Issue number6
StatePublished - Mar 28 2012


  • Brooks' theorem
  • Critical graphs
  • Graph coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Graphs with chromatic number close to maximum degree'. Together they form a unique fingerprint.

Cite this