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 -