Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-4 |
| Number of pages | 4 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 15 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jul 6 2008 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics