Edge-choosability of cubic graphs and the polynomial method
Andrea Marie Spencer · Summit (Simon Fraser University) · 2010
A graph is k-edge-choosable if for any assignment of a list of at least k colours to each edge, there is a proper edge-colouring of the graph such that each edge is assigned a colour from its list.Any loopless cubic graph G is known to be 4-edge-choosable by an extension of Brooks' Theorem.In this thesis, we give an alternative proof by relating edge-choosability to the coefficients of a certain polynomial using Alon and Tarsi's Combinatorial Nullstellensatz.We interpret these coefficients combinatorially to show that the required edge-colourings exist.Moreover, we show that if G is planar with c cut edges, then all but 3c of the edges of G can be assigned lists of at most 3 colours.I would like to thank Dr. Luis Goddyn, my senior supervisor, for his support, guidance and patience, as well as for suggesting this problem.