Partitions and Edge Colourings of Multigraphs

Abstract

Erdős and Lovász conjectured in 1968 that for every graph $G$ with $\chi(G)>\omega(G)$ and any two integers $s,t\geq 2$ with $s+t=\chi(G)+1$, there is a partition $(S,T)$ of the vertex set $V(G)$ such that $\chi(G[S])\geq s$ and $\chi(G[T])\geq t$. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for line graphs of multigraphs.