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
Link To Document :
بازگشت