2020/08/18 by Wang, Yue, Yu, Gexin
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2008.08017
Let s≥2 and t≥2 be integers. A graph G is (s,t)-splittable if V(G) can be partitioned into two sets S and T such that χ(G[S])≥ s and χ(G[T])≥ t. The well-known Erdős-Lovász Tihany Conjecture from 1968 states that every graph G whose chromatic number χ(G)=s+t-1 is more than its clique number ω(G) is (s,t)-splittable. In this paper, we prove an enhanced version of the Erdős-Lovász Tihany Conjecture for graphs with independence number two. That is, for every graph G with χ(G)=s+t-1>ω(G)+1 is (s,t+1)-splittable. There are examples showing that this result is best possible.