Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs

Abstract

The Erdős-Lovász Tihany Conjecture states that any $G$ with chromatic number $\chi (G)=s+t-1>\omega (G)$, with $s,t\ge 2$ can be split into two vertex-disjoint subgraphs of chromatic number $s,t$ respectively. We prove this conjecture for pairs $(s,t)$ if $t\le s+2$, whenever $G$ has a $K_s$, and for pairs $(s,t)$ if $t\le 4s-3$, whenever $G$ contains a $K_s$ and is claw-free. We also prove the Erdős Lovász Tihany Conjecture for the pair $(3,10)$ for claw-free graphs.

18 pages, 3 figures