## 2 Background, and a Preliminary Result  
For basic definitions in graph theory, we refer to the text of [PERSON] [3]. Before briefly surveying some previous research on colour graphs we recall the definition of \(col(G)\), _the colouring number of \(G\)_. Let \(\pi=x_{1},x_{2},\ldots,x_{n}\) be an ordering of the vertices of \(G\). Let \(H_{i}\) be  
Figure 1: Three different vertex orderings of \(P_{4}\) with associated \(Can_{3}^{\pi}(P_{4})\). In each case the colourings are canonical with respect to the given vertex ordering from left to right. the subgraph of \(G\) induced by \(\{x_{1},x_{2},\ldots,x_{i}\}\), for \(i=1,2,\ldots,n\). Define \(D_{\pi}=\max_{1\leq i\leq n}d_{H_{i}}(x_{i})\). Then \(col(G)=\min_{\pi}D_{\pi}+1\). Equivalently, \(col(G)=1+\max\delta(H)\), where the maximum is taken over all subgraphs of \(G\). The quantity \(col(G)\) is an upper bound on the number of colours needed if the greedy colouring algorithm is applied to \(G\) and vertices are coloured in the order \(\pi\). Hence \(\chi(G)\leq col(G)\leq\Delta(G)+1\). For \(k\geq 1\), let \(\mathcal{F}_{k}(G)\) be the set of \(k\)-colourings of a graph \(G\). The \(k\)_-colouring graph of \(G\)_, denoted \(\mathcal{C}_{k}(G)\), has vertex set \(\mathcal{F}_{k}(G)\), with two \(k\)-colourings being adjacent if and only if they differ in the colour of exactly one vertex. For example, the 3-colouring graph of a path on four vertices is given in Figure 2. This is an example of a reconfiguration graph in which vertices represent feasible solutions to a problem and there is an edge between two solutions if one can be transformed to the other by some allowable reconfiguration rule. There is a vast literature on the complexity of reconfiguration problems, for example see [4; 5]. The graph \(\mathcal{C}_{k}(G)\) is the most studied of the various colour graphs (that is, among the different allowable sets of colourings, and different reconfiguration rules). Connectivity of \(\mathcal{C}_{k}(G)\) arises in random sampling of \(k\)-colourings, and approximating the number of \(k\)-colourings, for example see [6; 7; 8]. [PERSON], [PERSON], [PERSON] and [PERSON] proved that there is a least integer \(c_{0}\leq col(G)+1\) such that \(k\)-colouring graph of \(G\) is connected for all \(k\geq c_{0}\)[6] (also see [9]). It is NP-complete to decide if the 3-colouring graph of a bipartite graph is connected [10], but polynomial-time to decide if two 3-colourings of a bipartite graph belong to the same component of \(\mathcal{C}_{3}(G)\)[11]. Hamiltonicity of the \(k\)-colouring graph was first considered in [12], wherein it was proved that there is always a least integer \(k_{0}\leq col(G)+2\) such that the \(k\)-colouring graph of the graph \(G\) is Hamiltonian for all \(k\geq k_{0}\). The number \(k_{0}\) is known for complete graphs, trees and cycles [12], 2-trees [13], complete bipartite graphs [14], and some complete multipartite graphs [15]. For other results on \(C_{k}(G)\), see [16], and for related results concerning the graph of \(L(2,1)\)-labellings (colourings with additional conditions), see [17]. The _Bell \(k\)-colouring graph of \(G\)_, denoted \(\mathcal{B}_{k}(G)\), has as vertices the partitions of \(V(G)\) into at most \(k\) independent sets, with two of these being adjacent when there is a vertex \(x\) such that these partitions are equal when restricted to \(G-x\). The Bell \(3-\) colouring graph of the path on four vertices is given in Figure 3. Bell \(k\)-colouring graphs are staudied in [18], as is the _Stirling \(\ell\)-colouring graph of \(G\)_, the subgraph of \(\mathcal{B}_{|V|}(G)\) induced by the partitions with exactly \(\ell\) cells. It is proved that \(\mathcal{B}_{|V|}(G)\) is Hamiltonian for every graph \(G\) except \(K_{n}\) and \(K_{n}-e\), and the quantity \(|V|\) is the best possible.