• Title of article

    Graphs with chromatic number close to maximum degree

  • Author/Authors

    Kostochka، نويسنده , , Alexandr. V. and Rabern، نويسنده , , Landon and Stiebitz، نويسنده , , Michael، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2012
  • Pages
    9
  • From page
    1273
  • To page
    1281
  • Abstract
    Let G be a color-critical graph with χ ( G ) ≥ Δ ( G ) = 2 t + 1 ≥ 5 such that the subgraph of G induced by the vertices of degree 2 t + 1 has clique number at most t − 1 . We prove that then either t ≥ 3 and G = K 2 t + 2 or t = 2 and G ∈ { K 6 , O 5 } , where O 5 is a special graph with χ ( O 5 ) = 5 and | O 5 | = 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].
  • Keywords
    graph coloring , Brooks’ Theorem , critical graphs
  • Journal title
    Discrete Mathematics
  • Serial Year
    2012
  • Journal title
    Discrete Mathematics
  • Record number

    1599920