Edge-choosability of cubic graphs and the polynomial method

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.