  For a positive integer k and a graph G, we consider proper vertex-colourings
of G with k colours in which all k colours are actually used. We call such a
colouring a strong k-colouring. The strong k-colour graph of G, S_k(G), is the
graph that has all the strong k-colourings of G as its vertex set, and two
colourings are adjacent in S_k(G) if they differ in colour on only one vertex
of G. In this paper, we show some results related to the question : For what G
and k is S_k(G) connected ?
