Edge-choosability of cubic graphs and the polynomial method
作者： Andrea Marie Spencer
DOI:
关键词:
摘要: A graph is k-edge-choosable if for any assignment of a list at least k colours to each edge, there proper edge-colouring the such that edge assigned colour from its list. Any loopless cubic G known be 4-edge-choosable by an extension Brooks’ Theorem. In this thesis, we give alternative proof relating edge-choosability coefficients certain polynomial using Alon and Tarsi’s Combinatorial Nullstellensatz. We interpret these combinatorially show required edge-colourings exist. Moreover, planar with c cut edges, then all but 3c edges can lists most 3 colours.
参考文章(14)
Noga Alon, Restricted colorings of graphs Surveys in combinatorics, 1993. pp. 1- 33 ,(1993) , 10.1017/CBO9780511662089.002
Bjarne Toft, Tommy R Jensen, Graph Coloring Problems ,(1994)
Douglas Brent West, Introduction to Graph Theory ,(1995)
Wiley‐Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Inc.. pp. 335- 336 ,(2011) , 10.1002/9781118032718.SCARD
Roland Häggkvist, Amanda Chetwynd, Some upper bounds on the total and list chromatic numbers of multigraphs Journal of Graph Theory. ,vol. 16, pp. 503- 516 ,(1992) , 10.1002/JGT.3190160510
B. Bollobás, A. J. Harris, List-colourings of graphs Graphs and Combinatorics. ,vol. 1, pp. 115- 127 ,(1985) , 10.1007/BF02582936
F. Galvin, The list chromatic index of a bipartite multigraph Journal of Combinatorial Theory, Series B. ,vol. 63, pp. 153- 158 ,(1995) , 10.1006/JCTB.1995.1011
Arthur A Drisko, On the Number of Even and Odd Latin Squares of Orderp+1 Advances in Mathematics. ,vol. 128, pp. 20- 35 ,(1997) , 10.1006/AIMA.1997.1623
M. N. Ellingham, Luis Goddyn, List edge colourings of some 1-factorable multigraphs Combinatorica. ,vol. 16, pp. 343- 352 ,(1996) , 10.1007/BF01261320
N. Alon, M. Tarsi, Colorings and orientations of graphs Combinatorica. ,vol. 12, pp. 125- 134 ,(1992) , 10.1007/BF01204715