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 - http://www.scopus.com/inward/record.url?scp=4043160682&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=4043160682&partnerID=8YFLogxK
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 -