Edge-choosability of cubic graphs and the polynomial method

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2010
Authors/Contributors
Abstract
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
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 summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd5922.pdf 1.91 MB