## 4 Bipartite Graphs  
We now show that, once \(k\) is sufficiently large, there is always a vertex ordering such that the canonical \(k\)-colouring graph of a bipartite graph is connected. We then show that the bound given is the best possible. **Theorem 3**: _Let \(G\) be a bipartite graph on \(n\) vertices, then there exists an ordering \(\pi\) of the vertices such that \(\operatorname{Can}_{t}^{\pi}(G)\) is connected for \(t\geq n/2+1\)._  
Suppose \(G\) has bipartition \((A,B)\), where \(|A|\geq|B|\). Choose \(a\in A,b\in B\), such that \(ab\in E(G)\). Define \(\pi\) to be \(a,b,B-b,A-a\). That is vertex \(a\) is coloured first, \(b\) is coloured second, the rest of \(B\) are the third through \((|B|+1)\)st vertices to be coloured, the rest of \(A\) are the \((|B|+2)\)nd through \(n\)th vertices to receive colours. Label the vertices \(v_{1},v_{2},\ldots v_{n}\) according to this order. The standard two colouring \(s:V\to\{1,2\}\) is \(s(v_{j})=1\) if \(j=1\) or \(j\geq|B|+2\), and \(s(v_{j})=2\) otherwise. The method will be to show that any colouring \(c:V\to\{1,2,\ldots,t\}\) can be obtained from the standard \(2\)-colouring \(s\) in a finite number of steps. First, suppose colour \(1\) is only used on vertices of \(A\). In this case the colouring \(c\) can be transformed into \(s\) as follows. Recolour (if necessary) each vertex of \(A\) to colour \(1\) by recolouring from vertex \(v_{n}\) down to \(v_{|B|+2}\), and then recolour each vertex of \(B\) to colour \(2\) by recolouring from vertex \(v_{|B|+2}\) down to \(v_{2}\). It is clear that at every stage there is a proper colouring. If colour \(1\) is used on vertices in both parts then the number of colours used on \(B\) is at most \(|B|\leq n/2\). Suppose exactly \(r\leq n/2<t\) colours (including colour \(1\)) are used on vertices in \(B\), and let \(x_{i}\) be the number of the first vertex to receive colour \(i\), \(i=1,\ldots r\). That is \(c(v_{x_{i}})=i\) and for all \(j<i\), \(c(v_{j})<i\). Clearly \(x_{1}=1,x_{2}=2\), and since \(c\) is a canonical colouring \(x_{1}<x_{2}<x_{3}<\cdots<x_{r}\). Set \(x_{r+1}=|B|+2\). We will use the \(x_{i}\) to define an intermediate colouring \(c^{\prime}\) by \(c^{\prime}(v_{j})=i\,\mathrm{if}\,x_{i}\leq j<x_{i+1}\leq n\), for \(j=1,2,\ldots,n\). This is a proper colouring because no colour is used on vertices in both parts \(B\) and \(A\). It uses \(r+1\leq t\) colours in total. The colours are used in numerical order, so it is canonical. The proof is completed by showing that the standard colouring \(s\) can be transformed to colouring \(c^{\prime}\) and colouring \(c^{\prime}\) can be transformed to colouring \(c\). Since colouring \(c^{\prime}\) does not use any colour on both parts, the standard colouring \(s\) can be transformed to \(c^{\prime}\) by changing the colours on \(v_{1}\) to \(v_{n}\) in order, if needed. That is change the colour on vertex \(v_{m}\) from \(s(v_{m})\) to the colour \(c^{\prime}(v_{m})\) for \(m=1,\ldots,n\). Next transform \(c^{\prime}\) to \(c\). Do this by passing through the vertices from \(v_{1}\) to \(v_{n}\)\(r\) times, once for each of the \(r\) colours used in \(c\). On the \(k\)th pass change vertices to colour \(k\) if they are colour \(k\) in \(c\). That is, in pass \(k\), step \(m\) we will change the colour of vertex \(v_{m}\), only if \(c(v_{m})=k\). We need to show that this gives a proper canonical colouring at every step. Let \(s_{km}\) be the colouring obtained after the \(m\)th step in the \(k\)th pass. Then  
\[s_{km}(v_{j})=\left\{ \begin{array}{ll}c(v_{j})&\mbox{ if }c(v_{j})<k,\mbox{ or if }c(v_{j})=k\,\mbox{and}\,j\leq m,\\ c^{\prime}(v_{j})&\mbox{ otherwise.}\end{array} \right.\]  
To see that each \(s_{km}\) is proper, we must show that, \(\{v_{j}|s_{km}(v_{j})=i\}\), the set of vertices coloured \(i\), is independent for all colours \(i=1,2,\ldots,r+1\) and all \(s_{km}\). For \(i<k\), the set of vertices coloured \(i\) in \(s_{km}\) equals the set of vertices coloured \(i\) in \(c\).