Connectedness of the graph of vertex-colourings.

Abstract

For a positive integer <i>k</i> and a graph <i>G</i>, the <i>k</i>-colour graph of <i>G</i> is the graph that has the proper <i>k</i>-vertex-colourings of G as its vertex set, and two <i>k</i>-colourings are joined by an edge in the <i>k</i>-colour graph if they differ in colour on just one vertex of <i>G</i>. In this note some results on the connectivity of the <i>k</i>-colour graph are proved. In particular it is shown that if <i>G</i> has chromatic number <i>k</i>=2 or 3, then the <i>k</i>-colour graph is not connected. On the other hand, for <i>k</i>>3 there are graphs with chromatic number <i>k</i> for which the <i>k</i>-colour graph is not connected, and there are <i>k</i>-chromatic graphs for which the <i>k</i>-colour graph is connected.