Title of article :
The Erdős–Lovász Tihany conjecture for quasi-line graphs
Author/Authors :
Balogh، نويسنده , , Jَzsef and Kostochka، نويسنده , , Alexandr V. and Prince، نويسنده , , Noah and Stiebitz، نويسنده , , Michael، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
7
From page :
3985
To page :
3991
Abstract :
Erdős and Lovász conjectured in 1968 that for every graph G with χ ( G ) > ω ( G ) and any two integers s , t ≥ 2 with s + t = χ ( G ) + 1 , there is a partition ( S , T ) of the vertex set V ( G ) such that χ ( G [ S ] ) ≥ s and χ ( G [ T ] ) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.
Keywords :
graph coloring , quasi-line graphs , independence number , Double-critical graphs
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1598894
Link To Document :
بازگشت