Partitions and edge colourings of multigraphs

Alexandr V. Kostochka, Michael Stiebitz

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1-4
Number of pages4
JournalElectronic Journal of Combinatorics
Volume15
Issue number1
DOIs
StatePublished - Jul 6 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Partitions and edge colourings of multigraphs'. Together they form a unique fingerprint.

Cite this