## 2 Background, and a Preliminary Result
It is also proved that the Bell \(k\)-colouring graph of a tree with at least four vertices is Hamiltonian for all \(k\geq 3\), and the Stirling \(\ell\)-colouring graph of a tree on at least \(n\geq 1\) vertices is Hamiltonian for all \(\ell\geq 4\)  
Figure 2: \(\mathcal{C}_{3}(P_{4})\), the 3-Colouring Graph of \(P_{4}\). The vertices are labeled by the colourings of the path. The graph \(\text{Can}_{k}^{\pi}(G)\) is a spanning subgraph of \(\mathcal{B}_{k}(G)\); the restriction to canonical colourings eliminates some edges of \(\mathcal{B}_{k}(G)\). Thus results asserting connectivity or Hamiltonicity of \(\text{Can}_{k}^{\pi}(G)\) imply connectivity or Hamiltonicity of \(\mathcal{B}_{k}(G)\), respectively. Since at most \(n\) colours can be assigned to the vertices of an \(n\)-vertex graph \(G\), it follows that \(\mathcal{B}_{k}(G)=\mathcal{B}_{n}(G)\) and \(\text{Can}_{k}^{\pi}(G)=\text{Can}_{n}^{\pi}(G)\) for all \(k\geq n\). Canonical \(k\)-colouring graphs were first considered in [1]. For every tree \(T\) there exists an ordering \(\pi\) of the vertices such that the canonical \(k\)-colouring graph of \(T\) with respect to \(\pi\) is Hamiltonian for all \(k\geq 3\). The canonical \(3\)-colouring graph of the cycle \(C_{n}\) is disconnected for all vertex orderings \(\pi\), while for each \(k\geq 4\) there exists an ordering \(\pi\) for which \(\text{Can}_{k}^{\pi}(C_{n})\) is connected. It is an open problem to find general conditions on \(k\) and \(\pi\) such that \(\text{Can}_{k}^{\pi}(G)\) is connected. Most results are negative assertions about certain vertex orders \(\pi\). In [1] it was proved that if \(G\) is connected, but not complete then there is always a vertex ordering \(\pi\) such that \(\text{Can}_{k}^{\pi}(G)\) is disconnected for all \(k\geq\chi(G)+1\). In particular, the graph \(\text{Can}_{k}^{\pi}(G)\) is disconnected whenever the first three vertices \(u,v,w\) of the vertex ordering \(\pi\) are such that \(uv\
ot\in E\) but \(uw,vw\in E\). Our first proposition generalizes that statement. Proposition 1: _Let \(\pi=v_{1},v_{2},\ldots,v_{n}\) be a vertex ordering of \(G\). If there exists \(i\geq 3\) such that \(v_{i}\) is adjacent to each of \(v_{1},v_{2},\ldots,v_{i-1}\), and the subgraph of \(G\) induced by \(\{v_{1},v_{2},\ldots,v_{i}\}\) is not complete, then \(\text{Can}_{k}^{\pi}(G)\) is disconnected for all \(k\geq\chi(G)+1\)._  
Proof: Let \(H_{i}\) be the subgraph of \(G\) induced by \(\{v_{1},v_{2},\ldots,v_{i}\}\). Since \(H_{i}\) is not complete, \(\chi(H_{i})<i\). Let \(c_{1}\) be a canonical \(\chi(G)\)-colouring of \(G\) with respect to \(\pi\). Then \(c_{1}(v_{i})=1+\max\{c_{1}(v_{1}),c_{1}(v_{2}),\ldots,c_{1}(v_{i-1})\). Furthermore, if \(c_{2}\) is an adjacent colouring in \(\text{Can}_{k}^{\pi}(G)\) then it differs on only one vertex. The colour of \(v_{i}\) cannot change (because we are only considering canonical colourings) so \(c_{2}\) must differ on a vertex other than \(v_{i}\). It follows that the vertex \(v_{i}\) is assigned the same colour in any canonical colouring that is joined to \(c_{1}\) by a path. Suppose first that \(c_{1}\) assigns the same colour to two of \(v_{1},v_{2},\ldots,v_{i-1}\), say \(c_{1}(v_{a})=c_{1}(v_{b})\) for some \(a,b<i\). Then, there is a (non-canonical) \(\chi(G)+1\) colouring of \(G\) in which \(v_{b}\) is coloured with colour \(\chi(G)+1\), and all other vertices, \(v_{j}\) for \(j<i\) are assigned the same colour as in \(c_{1}\). Let \(c_{2}\) be the equivalent canonical colouring to this with respect to \(\pi\) (defines the same partition of \(V(G)\)). Then \(c_{2}(v_{i})=1+c_{1}(v_{i})\). Hence, there is no path in \(\text{Can}_{k}^{\pi}(G)\) joining \(c_{1}\) and \(c_{2}\). Now assume \(c_{1}\) assigns distinct colours to each of \(v_{1},v_{2},\ldots,v_{i-1}\). Since \(H_{i}\) is not complete, it has a pair of non-adjacent vertices. There is a \(\chi(G)+1\) colouring of \(G\) in which these two vertices are assigned the same colour, and all other vertices are assigned the same colour as in \(c_{1}\).