Title of article :
Hadwiger’s conjecture for line graphs
Author/Authors :
Reed، نويسنده , , Bruce and Seymour، نويسنده , , Paul، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Pages :
4
From page :
873
To page :
876
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)=∅ and V(Ai∩Aj)≠∅ for 1≤i<j≤k.
Journal title :
European Journal of Combinatorics
Serial Year :
2004
Journal title :
European Journal of Combinatorics
Record number :
1549466
Link To Document :
بازگشت