Colouring complexes of planar triangulations and the line graphs of cubic graphs

In order to study the parity of a k-colouring, Tutte introduced the notion of a k-colouring complex in 1969. Given a k-colourable graph X, the k-colouring complex Bk(X) is the graph which has all the independent sets which are colour classes of X as its vertices and two vertices A and B in V (Bk(X)) joined by an edge if the colour classes A and B appear together in a k-colouring of X. Subsequently, Fisk proved that the graph Bk(X) is k-colourable and discovered infinite families of graphs for which Bk(Bk(X)) is isomorphic to X. In this thesis, we resolve a question Tutte posed about the 4-colouring complex at one of his final public lectures in 1999. He asked whether the 4-colouring complex of a planar triangulation could have two components in which all colourings have the same parity. In response, we construct triangulations of the plane whose 4-colouring complexes have arbitrarily many even and odd components. Furthermore, we exhibit an infinite family of 4-connected triangulations of the plane whose 4-colouring complexes have an arbitrarily large number of even components, as well as a number of 5-connected triangulations of the plane whose 4-colouring complexes have at least two components in which all colourings have the same parity. In the later chapters of this thesis, we continue our study of the k-colouring complex, discovering many new infinite families of graphs X for which Bk(Bk(X)) is isomorphic to X. We call these graphs reflexive graphs. Most notably, if G is a 3-edge-colourable, connected, cubic (possibly including half-edges) outerplanar graph, we prove that L(G) is reflexive if and only if G is triangle-free. In order to establish this result, we show how to reduce questions about the reflexivity of a connected graph to questions about the reflexivity of its 2-edge-connected components. Then we determine conditions under which subdividing an edge preserves reflexivity. These two novel theorems are of independent interest. In particular, we apply the latter theorem to prove that theta graphs have reflexive line graphs.