Article
The Erdős-Lovász Tihany Conjecture for Quasi-Line Graphs
Publications & Research
(2009)
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
- Erdős-Lovász Tihany Conjecture,
- quasi-line graphs,
- graphs,
- conjecture,
- discrete mathematics
Disciplines
Publication Date
January 1, 2009
Citation Information
Balogh, J., Kostochka, A.V., Prince, N., & Stiebitz, M. (2009). The Erdos-Lovasz Tihany conjecture for quasi-line graphs. Discrete Mathematics, 309(12), 3985-3991.
At the time of publication, Noah Prince was affiliated with the University of Illinois at Urbana-Champaign.