Partitions and edge colourings of multigraphs (Q1010682)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitions and edge colourings of multigraphs |
scientific article |
Statements
Partitions and edge colourings of multigraphs (English)
0 references
7 April 2009
0 references
Summary: Erdős and Lovász conjectured in 1968 (see Problem 5.12 in [\textit{T.R.\, Jensen} and \textit{B. Toft}, Graph colouring problems, New York: John Wiley \& Sons (1995; Zbl 0855.05054)]) 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.
0 references