MATH 488/489: Nick Brettell's sample projects

The complexity of list 3-colouring comb convex and chordal bipartite graphs

A k-colouring of a graph is an assignment of one of k colours to each vertex so that no two adjacent vertices are assigned the same colour. Graph colouring problems have been a driving force behind much of the development of graph theory, and are well studied. Nonetheless, there are still things we don't know. Rather than a fixed palette of the same k colours for each vertex, we can consider a list colouring, where each vertex is assigned a colour from a palette of colours, but this palette may vary from vertex to vertex in the graph. A graph is k-choosable if it is list colourable for every possible assignment of palettes where each vertex has k possible colours. In general, determining if a graph is 3-choosable appears to be computationally difficult. The goal of this project is to determine if that remains true for two particular subclasses of bipartite graphs: comb convex graphs, and chordal bipartite graphs.

On excluded minors for matroids representable over GF(5).

Finding excluded minor characterisations for classes of representable matroids (analogous to Kuratowski's theorem for the class of planar graphs) is an area of much interest to matroid theorists. Arguably the biggest open problem in this area is finding the complete list of excluded minors for matroids representable over the 5-element field (the analogous problem for smaller fields has been resolved, most recently for the 4-element field, for which the authors won the Fulkerson Prize). One strategy towards solving this problem was outlined by Pendavingh and van Zwam, and the first step is to find the excluded minors for the subclass consisting only of GF(5)-representable matroids with 6 inequivalent representations. Recent work (by myself, and with Oxley, Semple and Whittle) has reduced this to a search on matroids with 14 or 15 elements. There are two potential goals for this project: the first would be complete the aforementioned search on matroids with 14 or 15 elements. A second option would be to find all excluded minors for GF(5)-representable matroids of size 11 (so far, those up to size 10 are known). In either case, the project would involve a mix of matroid theory and computer programming (using Sage).