Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649333 | Discrete Mathematics | 2009 | 7 Pages |
Abstract
Erdős and Lovász conjectured in 1968 that for every graph GG with χ(G)>ω(G)χ(G)>ω(G) and any two integers s,t≥2s,t≥2 with s+t=χ(G)+1s+t=χ(G)+1, there is a partition (S,T)(S,T) of the vertex set V(G)V(G) such that χ(G[S])≥sχ(G[S])≥s and χ(G[T])≥tχ(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
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
József Balogh, Alexandr V. Kostochka, Noah Prince, Michael Stiebitz,