Enhancing the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs

Abstract

In this paper, we prove an enhanced version of the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs. That is, for every graph $G$ whose chromatic number $\chi (G)$ is more than its clique number $\omega (G)$ and for nonnegative integer $\ell$, any two integers $s,t\ge 3.5\ell +2$ with $s+t=\chi (G)+1$, there is a partition $(S,T)$ of the vertex set $V(G)$ such that $\chi (G[S])\ge s$ and $\chi (G[T])\ge t+\ell$. In particular, when $\ell =1$, we can obtain the same result just for any $s,t\ge 4$. The Erdős-Lovász Tihany conjecture is a special case when $\ell =0$.

References in corpus (1)

• A note on the double-critical graph conjecture