math.CO
Enhancing the Erd H o s Lov 'asz Tihany Conjecture for graphs with independence number two. Let s ge2 and t ge2 be integers. A graph G is (s,t) emph splittable if V(G) can be partitioned into two sets S and T such that chi(G S ) geq s and chi(G T ) geq t . The well known Erd H o s Lov 'asz Tihany Conjecture from 1968 states that every graph G whose chromatic number chi(G) s t 1 is more than its clique number omega(G) is (s,t) splittable. In this paper, we prove an enhanced version of the Erd H o s Lov 'asz Tihany Conjecture for graphs with independence number two. That is, for every graph G with chi(G) s t 1 omega(G) 1 is (s,t 1) splittable. There are examples showing that this result is best possible.