## 1 Introduction  
One definition of a \(k\)_-colouring_ of a graph \(G\) is as a function \(f:V(G)\to\{1,2,\ldots,k\}\) such that \(f(x)\
eq f(y)\) whenever \(xy\in E(G)\). Under this definition, \(k\)-colourings \(f_{1}\) and \(f_{2}\) are different whenever there exists a vertex \(x\) such that \(f_{1}(x)\
eq f_{2}(x)\). Each \(k\)-colouring \(f\) is equivalent to a \(k\)-tuple \((f^{-1}(1),f^{-1}(2),\ldots,f^{-1}(k))\) in which the set of non-empty components is a partition of \(V(G)\) into independent sets. A \(k\)-colouring \(f:V(G)\to\{1,2,\ldots,k\}\) is _canonical_ with respect to an ordering \(\pi=v_{1},v_{2},\ldots,v_{n}\) of the vertices of \(G\) if, whenever \(f(v_{i})=c\), every colour less than \(c\) has been assigned to some vertex that precedes \(v_{i}\) in \(\pi\). Thus \(v_{1}\) is necessarily assigned colour \(1\), and colour \(3\) can only be assigned to some vertex after colour \(2\) has been assigned to a vertex that appears earlier in the sequence \(\pi\). Note that canonical colourings may be very different than the colourings arising from applying the usual greedy colouring algorithm to \(G\) using the vertex ordering \(\pi\). Define an equivalence relation \(\sim\) on the set of \(k\)-colourings of \(G\) by \(f_{1}\sim f_{2}\) if and only if \(f_{1}\) and \(f_{2}\) determine the same partition of \(V(G)\) into independent sets. The set of canonical \(k\)-colourings of \(G\) with respect to \(\pi\) is then the set of representatives of the equivalence classes of \(\sim\) that are lexicographically least with respect to \(\pi\). Thus, canonical \(k\)-colourings exist for every \(k\geq\chi(G)\) and every proper colouring is equivalent to a canonical colouring. For an ordering \(\pi\) of the vertices of a graph \(G\), the _canonical \(k\)-colouring graph of \(G\)_, denoted \(\text{Can}_{k}^{\pi}(G)\), has vertex set equal to the set of canonical \(k\)-colourings of \(G\) with respect to \(\pi\), with two of these being adjacent when they differ in the colour assigned to exactly one vertex. While every ordering gives a set of representatives of the possible \(k\)-colourings, different orderings can lead to different canonical \(k\)-colourings graphs. Examples of the canonical \(3\)-colouring graph of the path on \(4\) vertices are given in Figure 1 for three different orderings of the vertices of the path. When a canonical colour graph is connected, any given canonical \(k\)-colouring can be reconfigured into any other via a sequence of recolourings which each change the colour of exactly one vertex. When it is Hamiltonian, there is a cyclic list that contains all of the \(k\)-colourings of \(G\) and consecutive elements of the list differ in the colour of exactly one vertex, that is, there is a cyclic Gray code of the \(k\)-colourings of \(G\). This paper is organized as follows. Relevant definitions and background information are reviewed in Section 2. A generalization of a lemma of [1] concerning vertex orderings such that \(\text{Can}_{k}^{\pi}(G)\) is disconnected for all \(k\geq\chi(G)\) is proved. Connectivity and Hamiltonicity of canonical colouring graphs of unions and joins of graphs are considered in Section 3. The main focus is on the situation where one of the graphs involved is a complete graph or a complement of a complete graph. For \(n\geq 1\) and any vertex ordering \(\pi\), canonical \(k\)-colourings of \(\overline{K}_{n}\) correspond exactly to partitions of \(\{1,2,\ldots,n\}\) with at most \(k\) cells. Our results give a Gray code listing of these partitions similar to that of [PERSON] [2]. Since the complete multipartite graph \(K_{n_{1},n_{2},\ldots,n_{t}}\) is the join of \(\overline{K}_{n_{1}},\overline{K}_{n_{2}},\ldots,\overline{K}_{n_{t}}\), our results show that there are vertex orderings \(\pi\) for which \(\text{Can}_{k}^{\pi}(K_{n_{1},n_{2},\ldots,n_{t}})\) is connected whenever \(k\geq r\).