Hadwiger's conjecture for line graphs

Bruce Reed; Paul Seymour

doi:10.1016/j.ejc.2003.09.020

Hadwiger's conjecture for line graphs

Bruce Reed
, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

26 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 A₁,...,A_k+1 of G, each with at least one edge, such that E(A_i ∩A_j)=0 and V(A_i∩A_j) ≠0 for 1≤i<j≤k.

Original language	English (US)
Pages (from-to)	873-876
Number of pages	4
Journal	European Journal of Combinatorics
Volume	25
Issue number	6
DOIs	https://doi.org/10.1016/j.ejc.2003.09.020
State	Published - Aug 2004

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2003.09.020

Cite this

@article{343458e7b1b240279f5f96ddebdd0b81,

title = "Hadwiger's conjecture for line graphs",

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",

author = "Bruce Reed and Paul Seymour",

note = "Funding Information: This research was supported by ONR grant N00014-97-1-0512 and NSF grant DMS 9701598.",

year = "2004",

month = aug,

doi = "10.1016/j.ejc.2003.09.020",

language = "English (US)",

volume = "25",

pages = "873--876",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "6",

}

TY - JOUR

T1 - Hadwiger's conjecture for line graphs

AU - Reed, Bruce

AU - Seymour, Paul

N1 - Funding Information: This research was supported by ONR grant N00014-97-1-0512 and NSF grant DMS 9701598.

PY - 2004/8

Y1 - 2004/8

N2 - 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

AB - 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

UR - https://www.scopus.com/pages/publications/4043160682

UR - https://www.scopus.com/pages/publications/4043160682#tab=citedBy

U2 - 10.1016/j.ejc.2003.09.020

DO - 10.1016/j.ejc.2003.09.020

M3 - Article

AN - SCOPUS:4043160682

SN - 0195-6698

VL - 25

SP - 873

EP - 876

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 6

ER -

Hadwiger's conjecture for line graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this