On the Erdös-Lovász Tihany Conjecture for Claw-Free Graphs

Abstract

In 1968, Erdös and Lovász conjectured that for every graph $G$ and all integers $s,t\ge 2$ such that $s+t-1=\ddot{I}‡(G)>\ddot{I}‰(G)$, there exists a partition $(S,T)$ of the vertex set of $G$ such that $\ddot{I}‡(G|S)\ge s$ and $\ddot{I}‡(G|T)\ge t$. For general graphs, the only settled cases of the conjecture are when $s$ and $t$ are small. Recently, the conjecture was proved for a few special classes of graphs: graphs with stability number 2 \cite{quasi-line}, line graphs \cite{line} and quasi-line graphs \cite{quasi-line}. In this paper, we consider the conjecture for claw-free graphs and present some progress on it.