Atlantic Graph Theory Seminar

A k-colouring of a graph G is an assignment of at most k colours to the vertices of a graph so that the ends of each edge of the graph get different colours. We consider the question: When it is possible to obtain any k-colouring from any other by changing the colour of one vertex at a time, while always having a k-colouring? This question is equivalent to asking whether the “reconfiguration graph” is connected: The reconfiguration graph of the k-colourings, denoted Rk(G), is the graph whose vertices are the k-colourings of G, and two colourings are adjacent in Rk(G) if they differ in colour on exactly one vertex. We call a graph recolourable if Rk(G) is connected for every k greater than its chromatic number.

We have characterized the graphs H such that all graphs G which don’t contain H as an induced subgraph are recolourable. We have done the same when two 4-vertex graphs are excluded as induced subgraphs (except for one class) and for some classes of graphs which exclude as an induced subgraph the path on 5 vertices.

Decompositions are important in solving optimization problems on structured classes of graphs. We have shown that modular decomposition and a stronger version of clique cutsets which we call tight clique cutsets can be used to show that certain classes are recolourable.

A k-colouring of a graph is called frozen if there is no vertex whose colour can be changed so that the result is still a k-colouring. A frozen colouring corresponds to an isolated vertex of the reconfiguration graph, and thus the existence of a frozen colouring is one way to show that a class of graphs is not recolourable. We have found several new classes of graphs with frozen colourings and an operation which transforms a k-chromatic graph with a frozen (k+1)-colouring into a (k+1)-chromatic graph with a frozen (k+2)-colouring.

This is joint work with Manoj Belavadi, Elias Hildred, Owen Merkel and Dewi Sintiari.