Mixing colourings in 2K_2-free graphs
share
The reconfiguration graph for the k-colourings of a graph G, denoted R_k(G), is the graph whose vertices are the k-colourings of G and two colourings are joined by an edge if they differ in colour on exactly one vertex. For any k-colourable P_4-free graph G, Bonamy and Bousquet proved that R_k+1(G) is connected. In this short note, we complete the classification of the connectedness of R_k+1(G) for a k-colourable graph G excluding a fixed path, by constructing a 7-chromatic 2K_2-free (and hence P_5-free) graph admitting a frozen 8-colouring. This settles a question of the second author.
READ FULL TEXT