Hadwiger's conjecture for line graphs

Bruce Reed, Paul Seymour

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

We prove that Hadwiger's conjecture holds for line graphs. Equivalently, we show that for every loopless graph G (possibly with parallel edges) and every integer k≥0, either G is k-edge-colourable, or there are k+1 connected subgraphs A1,...,Ak+1 of G, each with at least one edge, such that E(Ai ∩Aj)=0 and V(Ai∩Aj) ≠0 for 1≤i<j≤k.

Original languageEnglish (US)
Pages (from-to)873-876
Number of pages4
JournalEuropean Journal of Combinatorics
Volume25
Issue number6
DOIs
StatePublished - Aug 1 2004

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Hadwiger's conjecture for line graphs'. Together they form a unique fingerprint.

  • Cite this