Erdős-Lovász Tihany Conjecture for graphs with forbidden holes

Abstract

A hole in a graph is an induced cycle of length at least $4$. Let $s\ge 2$ and $t\ge 2$ be integers. A graph $G$ is $(s,t)$-splittable if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $\chi (G[S])\ge s$ and $\chi (G[T])\ge t$. The well-known Erdős-Lovász Tihany Conjecture from 1968 states that every graph $G$ with $\omega (G)<\chi (G)=s+t-1$ is $(s,t)$-splittable. This conjecture is hard, and few related results are known. However, it has been verified to be true for line graphs, quasi-line graphs, and graphs with independence number $2$. In this paper, we establish more evidence for the Erdős-Lovász Tihany Conjecture by showing that every graph $G$ with $\alpha (G)\ge 3$, $\omega (G)<\chi (G)=s+t-1$, and no hole of length between $4$ and $2\alpha (G)-1$ is $(s,t)$-splittable, where $\alpha (G)$ denotes the independence number of a graph $G$.

arXiv commentarXiv admin note: text overlap with arXiv:1607.06718, arXiv:1610.00636