The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs

József Balogh, Alexandr V. Kostochka, Noah Prince, Michael Stiebitz

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)3985-3991
Number of pages7
JournalDiscrete Mathematics
Issue number12
StatePublished - Jun 28 2009


  • Double-critical graphs
  • Graph coloring
  • Independence number
  • Quasi-line graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The Erdo{double acute}s-Lovász Tihany conjecture for quasi-line graphs'. Together they form a unique fingerprint.

Cite this