TY - JOUR
T1 - The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs
AU - Balogh, József
AU - Kostochka, Alexandr V.
AU - Prince, Noah
AU - Stiebitz, Michael
N1 - Funding Information:
The work of the first author was supported by NSF CAREER Grant DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 06139 and 07048, and OTKA grant 049398.
Funding Information:
The work of the second author was supported by NSF Grant DMS-06-50784 and grant 06-01-00694 of the Russian Foundation for Basic Research.
PY - 2009/6/28
Y1 - 2009/6/28
N2 - Erdo{double acute}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.
AB - Erdo{double acute}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.
KW - Double-critical graphs
KW - Graph coloring
KW - Independence number
KW - Quasi-line graphs
UR - http://www.scopus.com/inward/record.url?scp=67349162930&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67349162930&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2008.11.016
DO - 10.1016/j.disc.2008.11.016
M3 - Article
AN - SCOPUS:67349162930
SN - 0012-365X
VL - 309
SP - 3985
EP - 3991
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 12
ER -