- This event has passed.

# Atlantic Graph Theory Seminar

## September 25, 2024 @ 3:00 pm - 4:30 pm

**Recolouring Graphs: Decompositions, A Dichotomy Theorem and Frozen Colourings**

Speaker: Kathie Cameron, Wilfrid Laurier University

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.

Zoom link:

Meeting ID: 868 6149 9971

Passcode: 325258