List edge colourings of some 1-factorable multigraphs

被引:37
作者
Ellingham, MN
Goddyn, L
机构
[1] VANDERBILT UNIV,DEPT MATH,NASHVILLE,TN 37240
[2] SIMON FRASER UNIV,DEPT MATH & STAT,BURNABY,BC V5A 1S6,CANADA
关键词
D O I
10.1007/BF01261320
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The List Edge Colouring Conjecture asserts that, given any multigraph G with chromatic index k and any set system {S-e:e is an element of E(G)} with each \S-e\ = k, we can choose elements s(e) is an element of S-e such that s(e) not equal s(f) whenever e and f are adjacent edges. Using a technique of Alon and Tarsi which involves the graph monomial Pi{xu-x(v):uv is an element of E} of an oriented graph, we verify this conjecture for certain families of 1-factcrable multigraphs, including 1-factorable planar graphs.
引用
收藏
页码:343 / 352
页数:10
相关论文
共 17 条
[1]   COLORINGS AND ORIENTATIONS OF GRAPHS [J].
ALON, N ;
TARSI, M .
COMBINATORICA, 1992, 12 (02) :125-134
[2]  
Alon N., 1993, LONDON MATH SOC LECT, V187, P1
[3]  
[Anonymous], 1891, Acta Mathematica, DOI DOI 10.1007/BF02392606
[4]   A NEW UPPER BOUND FOR THE LIST CHROMATIC NUMBER [J].
BOLLOBAS, B ;
HIND, HR .
DISCRETE MATHEMATICS, 1989, 74 (1-2) :65-75
[5]   A NOTE ON LIST-COLORINGS [J].
CHETWYND, A ;
HAGGKVIST, R .
JOURNAL OF GRAPH THEORY, 1989, 13 (01) :87-95
[6]  
Erdo P., 1980, Congr. Numer., P125
[7]   A SOLUTION TO A COLORING PROBLEM OF ERDOS,P. [J].
FLEISCHNER, H ;
STIEBITZ, M .
DISCRETE MATHEMATICS, 1992, 101 (1-3) :39-48
[8]   THE LIST CHROMATIC INDEX OF A BIPARTITE MULTIGRAPH [J].
GALVIN, F .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) :153-158
[9]  
HAGGKVIST R, IN PRESS COMBIN PROB
[10]   ON THE PENROSE NUMBER OF CUBIC DIAGRAMS [J].
JAEGER, F .
DISCRETE MATHEMATICS, 1989, 74 (1-2) :85-97