Connectedness of the graph of vertex-colourings (Q2470462)

The \(k\)-colour graph of \(G, k(G)\), is the graph that has the proper \(k\)-colourings of \(G\) as its vertex set, and two \(k\)-colourings are joined by an edge in \(k(G)\) if they differ in colour on just one vertex of \(G\). \(G\) is \(k\)-mixing if \(k(G)\) is connected. The authors show that if \(G\) has chromatic number \(k\) equal 2 or 3 then \(G\) is not \(k\)-mixing. Furthermore, for all \(k>3\) there exist graphs with chromatic number \(k\) that are not \(k\)-mixing and graphs with chromatic number \(k\) that are \(k\)-mixing. A characterization is provided for all positive integers \(L\) and sets \(P\) with \(\min P\geq L\) such that there exist graphs \(G\) with chromatic number equal to \(L\) that are \(k\)-mixing if and only if \(k\) is not in \(P\).