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 coeﬃcients of a certain polynomial using Alon and Tarsi’s Combinatorial Nullstellensatz. We interpret these coeﬃcients 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.
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact email@example.com.
Member of collection