Article ID Journal Published Year Pages File Type
4649333 Discrete Mathematics 2009 7 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,