## 4 Bipartite Graphs
First use any Hamilton path through the subgraph induced by \(\{c_{i}\cdot\ell|1\leq\ell\leq\ell_{i}\}\cup\{c_{i+1}\cdot\ell|1\leq\ell\leq \ell_{i}\}\) which starts at \(c_{i}\cdot 1\), and ends at \(c_{i+1}\cdot\ell_{i}\) and satisfies property (ii). Next, proceed as in the odd case alternating the direction of the Hamilton path, so that again the path through \(\{c_{i}+m\cdot\ell|m=0,1,\ldots,j\}\) ends at \(c_{i+j}\cdot 1\). In either case, the set of colours used on \(c_{i+m}\cdot\ell\) is identical for all \(m,\ell\) except possibly when \(\ell=\ell_{i}\), and the set of colours used on \(c_{i+2p}\cdot\ell_{i}\) is identical to the set of colours used on \(c_{i+2p+1}\cdot\ell_{i}\) and these colourings are adjacent in the path. That the last colouring in the path uses all \(k\) colours follows from the induction hypothesis. The Hamilton path for \(\operatorname{Can}_{n+1}^{\pi}(\overline{K}_{n+1})\) is obtained from the one of \(\operatorname{Can}_{n}^{\pi}(\overline{K}_{n+1})\) by appending \(c_{t}\cdot(n+1)\) to the last vertex in \(\operatorname{Can}_{n}^{\pi}(\overline{K}_{n+1})\), which will be of the form \(c_{t}\cdot\ell\). The properties for the Hamilton paths required in the above proof are similar to those studied by various authors in the context of Gray codes for set partitions. In [19] the authors give Gray codes for the set of restricted growth functions, which is the set of non-negative integer sequences \(\{a_{1}a_{2}\ldots a_{n}:a_{i+1}\leq\max\{a_{1},a_{2},\ldots,a_{i}\}+1\}\). While these Gray codes start with \(11\ldots 1\) and end with \(123\ldots n\), they do not have the property that at least two sequences in a row use the same set of integers (see for example Figure 5 in [19]). The set of bounded restricted growth functions is \(R_{b}(n)=\{a_{1}a_{2}\ldots a_{n}:a_{i+1}\leq\max\{a_{1},a_{2},\ldots,a_{i}\}+1 \text{ and }a_{i}\leq b\}\). [PERSON] and [PERSON] also considered Gray codes on \(R_{b}(n)\), but restrict their attention to strict and weak Gray codes which have the further property that successive elements can differ by only \(1\) (if strict) or \(2\) (weak) in the one position in which they differ. They show that such codes cannot exist. In the Gray codes considered here, successive sequences can differ in only one position, but the elements can differ by any amount. In other words, Theorem 4 says there is a (non strict, non weak) Gray Code for the set of bounded restricted growth functions, \(R_{b}(n)\), that satisfies properties (i) and (ii). There exists a vertex ordering \(\pi\) such that \(\operatorname{Can}_{k}^{\pi}(K_{n,m})\) has a Hamilton path for \(n,m\geq 2\), \(k\geq 3\). Proof. : Let \(K_{n,m}\) have bipartition \((A,B)\), where \(A=\{a_{1},\ldots a_{n}\}\), \(B=\{b_{1},\ldots b_{m}\}\). Let the vertex ordering \(\pi=a_{1}b_{1}a_{2}a_{3}\ldots a_{n}b_{2}b_{3}\ldots b_{m}\). By Theorem 4 there is a Hamilton path, \(x_{1},x_{2},\ldots x_{t}\), with properties (i) and (ii), in the canonical \(k\)-colouring graph of the subgraph induced by the restriction of \(\pi\) to its first \(n+1\) vertices, \(a_{1}b_{1}a_{2}a_{3}\ldots a_{n}\) (since \(\{a_{1},a_{2},\ldots,a_{n}\}\) is an independent set, and \(b_{1}\) will always be assigned the same colour in any canonical colouring). For each such colouring \(x_{i}\), let \(G(x_{i})\) be the subgraph of \(\operatorname{Can}_{k}^{\pi}(K_{n,m})\) consisting of the canonical colourings which are extensions of \(x_{i}\). Note that each subgraph \(G(x_{i})\) is isomorphic to a graph \(\operatorname{Can}_{k-r}^{\pi}(\overline{K}_{m})\), corresponding to the colourings of the vertices \(b_{1}b_{2}b_{3}\ldots b_{m}\) in the \(k-r\) colours not used on \(a_{1},a_{2},a_{3}\ldots a_{n}\) (starting with \(2\) which was the colour used on \(b_{1}\)), and also that \(V(\operatorname{Can}_{k}^{\pi}(K_{n,m}))=\cup_{i\leq i\leq t}V(G(x_{i}))\). The Hamilton path in \(\operatorname{Can}_{k}^{\pi}(K_{n,m})\) will be constructed by piecing together Hamilton paths from the \(G(x_{i})\) in the order \(i=1,2,\ldots,t\).