## 4 Bipartite Graphs
Thus \(\{v_{j}|s_{km}(v_{j})=i\}\) is an independent set for \(i\leq k-1\). For \(i>k\), the set of vertices coloured \(i\) in \(s_{km}\) is a subset of the set of vertices coloured \(i\) in \(c^{\prime}\) thus \(\{v_{j}|s_{km}(v_{j})=i\}\) is an independent set for \(i\geq k+1\). It remains to consider \(\{v_{j}|s_{km}(v_{j})=k\}\). The vertices coloured \(k\) under \(s_{km}\) are \(\{v_{j}|s_{km}(v_{j})=k\}=\{v_{j}|j\leq m,c(v_{j})=k\}\cup\{v_{j}|j>m,c^{\prime }(v_{j})=k\}\). When \(k=1\) then since \(x_{1}=1\) and \(x_{2}=2\), we get \(\{v_{j}|s_{km}(v_{j})=1\}\subseteq\{v_{j}|c(v_{j})=1\}\), for all \(m\) so this is an independent set. At the other end, when \(x_{k}\geq|B|+2\) all vertices coloured \(k\) by either colouring \(c\) or \(c^{\prime}\) will be in part \(A\). So \(\{v_{j}|s_{km}(v_{j})=k\}\) is independent for all \(m\). If \(2\leq x_{k}\leq|B|+1\) then \(c^{\prime}\) only assigns colour \(k\) to vertices in part \(B\). No vertex in part \(A\) is coloured \(k\) until the only vertices coloured \(k\) on part \(B\) are those coloured \(k\) under \(c\). There are two cases. * If \(m\leq|B|+1\) then all vertices coloured \(k\) in \(s_{km}\) are in \(B\) so the set is independent. * If \(m>|B|+1\), this means that the only vertices in \(B\) that are still coloured \(k\) are coloured \(k\) under \(c\), that is: \(|B|\cap\{v_{j}|s_{km}(v_{j})=k\}=|B|\cap\{v_{j}|c(v_{j})=k\}\). No vertices in \(A\) are coloured \(k\) under \(c^{\prime}\) so if \(v_{j}\in A\) and \(s_{km}(v_{j})=k\), then \(m>j\) and \(s_{km}(v_{j})=c(v_{j})=k\). Thus \(\{v_{j}|s_{km}(v_{j})=k\}\subseteq\{v_{j}|c(v_{j})=k\}\) which is independent. Finally we show the colourings are canonical. By construction, for all colours, \(i,c(v_{x_{i}})=c^{\prime}(v_{x_{i}})=s_{km}(v_{x_{i}})=i\), and no vertex before \(v_{x_{i}}\) is coloured \(i+1\) or higher in any of the colourings. Thus each of \(s_{km}\) is a canonical proper colouring. Consider the graph \(L_{n}=K_{n,n}-F\), where \(F\) is a perfect matching. In the \(n\)-colouring of \(L_{n}\) where the opposite ends of edges in \(F\) are assigned the same colour, every vertex has a neighbour of any different colour. Thus, if \(c\) is the canonical version of this colouring with respect to a vertex ordering \(\pi\), then \(c\) is an isolated vertex in \(\mathsf{Can}_{n}^{\pi}(L_{n})\). Since \(L_{n}\) has \(2n\) vertices, it follows that the lower bound in the above theorem is the best possible. By Corollary 7, there is always a vertex ordering \(\pi\) such that \(\mathsf{Can}_{k}^{\pi}(K_{n_{1},n_{2},\ldots,n_{r}})\) is connected. We now show that there is no Hamilton cycle, and frequently no Hamilton path, in the canonical \(k\)-colouring graph of a complete multipartite graph. By Corollary 4 it suffices to consider the case where \(n_{i}\geq 2\) for all \(i\). The specific example of \(\mathrm{Can}_{k}^{\pi}(K_{2,2,\ldots,2})\) will be considered in detail in Section 5. Proposition 4: _Let \(G=K_{n_{1},n_{2},\ldots,n_{r}}\), where \(n_{i}\geq 2\), for all \(i\). Then, for all vertex orderings \(\pi\) and \(k\geq r+1\),_  
1. \(\mathrm{Can}_{k}^{\pi}(G)\) _has a cut vertex and hence has no Hamilton cycle;_
2. _if_ \(r\geq 3\) _then_ \(\mathrm{Can}_{k}^{\pi}(G)\) _has no Hamilton path._  
Proof: We first prove statement 1. The colouring \(c\) where every vertex in the \(i\)th part gets colour \(i\) is a cut vertex. Note that no colour can be used on vertices in more than one part. Any colouring \(c_{i}\) where a vertex \(v_{i}\) in part \(i\) gets colour \(r+1\) cannot change to a colouring \(c_{j}\) where a vertex \(v_{j}\) in part \(j\) gets coloured \(r+1\) without first changing the colour of \(v_{i}\). If the colour \(r+1\) is removed from part \(i\) then no higher colour can be used without violating canonicity. So if there is a path from \(c_{i}\) to \(c_{j}\), it must pass through \(c\). We now prove statement 2. If \(\pi\) does not start with a maximum clique, then \(\mathrm{Can}_{k}^{\pi}(G)\) is disconnected by Proposition 1.