Erdos and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t > 2 with s + t = χ(G) +1, there is a partition (S, T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for line graphs of multigraphs.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics