ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 653-698
https://doi.org/10.26493/1855-3974.1813.7ae
(Also available at http://amc-journal.eu)
Reconfiguring vertex colourings of 2-trees
Michael Cavers, Karen Seyffarth
Department of Mathematics and Statistics, University of Calgary, Calgary, AB T2N1N4 Canada
Received 4 October 2018, accepted 8 October 2019, published online 16 December 2019
Let H be a graph and let k > x(H) be an integer. The k-colouring graph of H, denoted Gk (H), is the graph whose vertex set consists of all proper k-vertex-colourings (or simply k-colourings) of H using colours {1, 2,..., k}; two vertices of Gk (H) are adjacent if and only if the corresponding k-colourings differ in colour on exactly one vertex of H. If Gk (H) has a Hamilton cycle, then H is said to have a Gray code of k-colourings, and the Gray code number of H is the least integer k0(H) such that Gk (H) has a Gray code of k-colourings for all k > k0(H). Choo and MacGillivray determine the Gray code numbers of trees. We extend this result to 2-trees. A 2-tree is constructed recursively by starting with a complete graph on three vertices and connecting each new vertex to an existing clique on two vertices. We prove that if H is a 2-tree, then k0(H) = 4 unless H is isomorphic to the join of a tree T and a vertex u, where T is a star on at least three vertices, or the bipartition of T has two even parts; in these cases, k0(H) = 5.
Keywords: 2-trees, graph colouring, Gray codes, Hamilton cycles, reconfiguration problems. Math. Subj. Class.: 05C15, 05C45
1 Introduction
Let H be a graph and k a positive integer. We define a proper k-vertex-colouring of H as a function f: V(H) ^ {1,2,..., k} for which f (x) = f (y) for any xy G E(H). Since we are concerned only with proper k-vertex-colourings, we use the simpler term k-colouring, and refer to f (x) as the colour of x. For notation and terminology not defined here, the reader is referred to Bondy and Murty [1].
A graph H has a Gray code of k-colourings if it is possible to list all the k-colourings of H in such a way that consecutive colourings in the list (including the last and the first) differ on exactly one vertex of H, and the Gray code number of H is the least integer
E-mail addresses: mcavers@ucalgary.ca (Michael Cavers), kseyffar@ucalgary.ca (Karen Seyffarth)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
654
Ars Math. Contemp. 17 (2019) 493-514
k0(H) for which H has a Gray code of its k-colourings for all k > k0(H). Equivalently, we may define the k-colouring graph of H, denoted Gk (H), to be the graph whose vertices correspond to all k-colourings of H, and whose edges connect two k-colourings of H that differ on exactly one vertex of H. In this context, H has a Gray code of k-colourings if and only if Gk (H) has a Hamilton cycle, and the Gray code number of H is the the least integer k0(H) for which Gk(H) has a Hamilton cycle for all k > k0(H).
The k-colouring graph is an example of a reconfiguration graph. Such graphs are often used in the study of what are known as reconfiguration problems. Generally, a reconfiguration problem asks: given two (different) feasible solutions to a problem, can one solution be transformed to the other through a sequence of allowable moves, while maintaining feasibility at each stage? In the context of k-colourings, the k-colouring graph is connected if and only if any k-colouring can be reconfigured into any other k-colouring by re-colouring one vertex at a time in such a way that each intermediate colouring is a k-colouring. Recently, reconfiguration problems have been receiving wide attention, and have been studied for various graph colouring problems [2, 3, 4, 10, 15], for dominating sets [12, 13, 18], and for various other graph problems including vertex covers, cliques, and independent sets [14].
The k-colouring graph arises in the context of theoretical physics, where it is the graph of the Glauber dynamics Markov chain; the goal is to find efficient algorithms for almost uniform sampling of k-colourings of graphs [16]. The Glauber dynamics Markov chain converges to the uniform distribution provided that the k-colouring graph is connected, prompting Cereceda, van den Heuvel and Johnson [4] to ask the question: given a graph H and a positive integer k, is Gk (H) connected? They prove that if H has chromatic number k G {2, 3}, then Gk (H) is never connected, whereas for k > 4, there are k-chromatic graphs H for which Gk (H) is connected, and other k-chromatic graphs H for which Gk (H) is not connected. In general, they prove that Gk(H) is connected for all k > col(H) + 1, where col(H), the colouring number of H, is defined as col(H) := max{^(G) | G C H} + 1. A slightly weaker version of this result is proven in [8].
Choo and MacGillivray [6] initiated the study of Hamilton cycles in k-colouring graphs by proving that the Gray code number of H is well defined, i.e., Gk (H) has a Hamilton cycle for all k > col(H) + 2. This gives the upper bound k0 (H) < col(H) + 2. Note that if T is a tree, then col(T) = 2 and G2(T) is disconnected; hence 3 < ko(T) < 4. Choo and MacGillivray [6] determine which trees have k0 (T) = 3 and which have k0(T) = 4. In particular, they prove that if T is a tree, then k0(T) = 3 unless T = K1j2£, for I > 1, in which case k0(T) = 4. They also determine the Gray code numbers of complete graphs and cycles. Celaya, Choo, MacGillivray and Seyffarth [3] establish the Gray code numbers of complete bipartite graphs. Haas [11] studies a variation of k-colouring graphs, namely, canonical colouring graphs, and uses techniques developed in [6] to show that canonical colouring graphs of trees have Hamilton cycles.
Given the results for trees and complete graphs, a natural question is to determine the Gray code numbers of k-trees. We use the definition of k-tree given in [9], that is, a k-tree is constructed recursively by starting with a complete graph on k + 1 vertices and connecting each new vertex to an existing clique on k vertices (hence a 1-tree is simply a connected acyclic graph). A vertex of degree k in a k-tree is called a leaf. Let H be a k-tree. Then it is clear that the chromatic number of H is x(H) = k + 1, and that Gk+1(H) is disconnected. Since every induced subgraph of H has a leaf, col(H) = k + 1. Thus it follows from [6, Theorem 3.4] that k0(H) < k + 3, and therefore k + 2 < k0(H) < k + 3. The problem
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
655
is therefore reduced to classifying k-trees into those with Gray code number k + 2 and those with Gray code number k + 3. The answer appears to be far from trivial. In the current paper, we provide a complete solution for 2-trees; the characterization can be stated in fairly non-technical language, but the proof involves numerous cases and generalizations of the techniques used in [3, 6]. The join of graphs G1 and G2, denoted by G1 V G2, is obtained from the disjoint union of Gi and G2 by adding all edges between vertices of Gi and vertices of G2.
Theorem 1.1. If H is a 2-tree then k0(H) = 4, unless H = T V {u} for some tree T and vertex u, where T is a star on at least three vertices or the bipartition of V (T) has two even parts; in these cases, k0(H) = 5.
The remainder of the paper is devoted to proving this theorem. We first characterize 2-trees of diameter two (Lemma 3.2). We then determine the 2-trees, H, of diameter two for which G4(H) has a Hamilton cycle (Lemmas 3.3 and 3.5). This is done by considering the structure of G3(T), where T is a tree (Lemmas A.2 and 3.6). We show that if H is a 2-tree with diameter at least three, then G4 (H) has a Hamilton cycle (Lemmas 6.3 and 6.4). To do so we describe a specific recursive procedure for constructing 2-trees of diameter at least three (Theorem 4.3).
2 Preliminaries
Definition 2.1. Let H be a graph, and let X and Y be disjoint subsets of V(H). We denote by [X, Y] the set of edges of H that have one end in X and the other end in Y.
Definition 2.2. Let H be a graph and L a function that assigns to each vertex v e V(H) a set of positive integers, L(v), called the list of v. An L-colouring of H (also called a list colouring of H with respect to L) is a (proper) colouring c: V(H) ^ N such that c(v) e L(v) for each v e V(H). We define the L-colouring graph of H, denoted GL(H), to be the graph whose vertex set consists of all L-colourings of H; two L-colourings are joined by an edge of GL(H) if they differ in colour on just one vertex of H.
Remark 2.3. If k > x(H) and L(v) := {1,2,..., k} for each v e V(H), then GL(H) = Gk (H), the k-colouring graph of H.
We use G □ H to denote the Cartesian product of graphs G and H, and Qn to denote the n-dimensional hypercube, defined as the Cartesian product of n copies of K2.
Remark 2.4. Let H1 and H2 be vertex disjoint graphs and let L be an assignment of lists to the vertices of H1 U H2. Then
GL(Hi U H2) = GL(Hi) □ Gl(H2).
Lemma 2.5. Let H be a 2-tree with clique X = {x1; x2,..., xi} where t < 3, and let L be an assignment of lists to the vertices of H so that
1.	|L(xi)| = 1 and L(x,) C {1, 2, 3, 4}, 1 < i < t;
2.	L(xj) = L(xj) for all 1 < i = j < t;
3.	L(v) = {1,2,3,4} for each v e V(H) \ X.
656
Ars Math. Contemp. 17 (2019) 493-514
Then GL(H) has a spanning tree T with A(T) < 4.
Proof. The proof is by induction on |V(H)|. For the basis, H = K3 with V(H) := jvi, v2,v3}. When I = 0, GL(H) = G4(K3), which has a Hamilton cycle [6, Theorem 4.1], so take T to be a Hamilton path in G4(K3). When I = 1, we may assume, without loss of generality, that L(v1) := {1} and L(v2) = L(v3) := {1,2,3,4}. Then Gl(H) = G3(K2), which has a Hamilton cycle [6, Theorem 4.1], so take T to be a Hamilton path in G3(K2). When I = 2, we may may assume, without loss of generality, that L(vi) := {1}, L(v2) := {2}, and L(vj) := {1, 2,3,4}. Then GL(H) = K2, and the result holds. Finally, when I = 3, we may assume, without loss of generality, that L(v1) := {1}, L(v2) := {2}, and L(v3) := {3}. Then GL(H) = K1, and the result holds.
Now suppose H is a 2-tree with |V(H)| > 3 and clique X = {x1;..., x.«}. Since I < 3, there is a leaf v e V(H) with v £ X, and thus H - v is a 2-tree containing the clique X. It follows by induction that GL(H - v) has a spanning tree T with A(T) < 4. Let V(Gl(H - v)) := {/q, /1,..., fN-1}, and for each / e V(GL(H - v)), let Fj C V(Gl(H)) be the set of L-colourings of H that agree with f on V(H - v). Then {Fq, F1,..., Fn-1} is a partition of the vertices of GL(H). Since v is a leaf of H, there are two ways to extend an L-colouring of H - v to an L-colouring of H, and hence for each j, 0 < j < N - 1, Fj = {aj, bj} is a clique.
For each edge // e E(T), there is a unique vertex w e V(H - v) for which fj (w) = fj(w). If wv £ E(H), then [Fj, Fj] consists of two disjoint edges, and the subgraph of Gl(H) induced by Fj U Fj is a 4-cycle. Otherwise, wv e E(H), so [Fj, Fj] has only one edge, and the subgraph of GL(H) induced by Fj U Fj is a path of length three. In both cases, label the edge fjfj in T with | [Fj, Fj] |.
Let S denote the spanning subgraph of GL(H) corresponding to the spanning tree T of Gl(H - v) as described above, that is, S has edge set
Since [Fj, Fj] is nonempty for each fjfj e E(T), S is connected. Also, since A(T) < 4 and [Fj; Fj] contains either one edge or two disjoint edges, A(S) < 5. Furthermore, since there are only two vertices adjacent to v in H, at most two edges incident to fj in GL(H-v) have label '1'.
Let S' be the graph obtained from S by deleting the edges aj bj for each fj e V (T) with dT(fj) = 4. Then A(S') < 4, since if aj e V(S) has ds(aj) = 5, then dT(fj) = 4, and thus dS/ (aj) =4. We also claim that S' is connected. To prove this, it suffices to show that there is a path in S' from ap to bp for each fp e V(T) with dT(fp) = 4. Suppose fp e V(T) has dT(fp) = 4. Construct a path, P, in T starting at fp, using edges labelled '2', and whose final vertex fq has dT(fq) < 4. Such a path exists since T has no cycles, and each degree four vertex in T is incident to at least two edges labelled '2'. The union
(J [Fj, Fj]) U {ajbj | 0 < j < N - 1}.
fifj £E(T)	/
gives us a path in S' from ap to b.
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
657
Therefore, S' is a connected spanning subgraph of GL(H), and thus S' has a spanning tree T that is also a spanning tree of GL(H). Since A(S') < 4, A(T) < 4, thus completing the proof of the lemma.	□
The result in Lemma 2.5 is best possible in that A(T) cannot be reduced from four to three, as illustrated in the following example. Let D denote the unique 2-tree of diameter three on six vertices, with vertices labelled as shown in Figure 1(a).
u 2
U1
u4
u 3
U 6
U 5
(a) D
3412
3413 3423 3421
3123
3124 3143 3142
(b) GL(D)
4312 4314 4324 4321
4123
4124 4134 4132
Figure 1: The 2-tree D and GL(D).
Let L: V(D) ^ {1, 2,3,4} be defined as follows.
L(U1) := {1},
L(u2) := {2}, and
L(ui) := {1, 2, 3, 4} for 3 < i < 6.
If f is an L-colouring of D, then f (u1) = 1 and f (u2) = 2, and thus we may denote the vertices of GL(D) by strings ijki where f (u3) = i, f (u4) = j, f (u5) = k and f (u6) = I. Using this convention, GL(D) is depicted in Figure 1(b). Notice that GL(D) is unicyclic, and has exactly two nonadjacent vertices of degree four, '3123' and '4124'. Thus every spanning tree of GL(D) has a vertex of degree four.
As part of their proof [6, Theorem 5.5], Choo and MacGillivray prove the following.
Remark 2.6. Let G be a graph with vertex partition {F0, F1,..., FN_1}, such that
(i)	G[Fi] is a 4-cycle for each i, 0 < i < N - 1;
(ii)	G[Fi_1 U Fi] is isomorphic to either P4 □ K2 or Q3 for each i, 1 < i < N — 1;
(iii)	if G[Fi_1 U Fi] and G[Fi U Fm] are both isomorphic to P4 □ K2, then G[Fi_1 U Fi U Fi+1] is not isomorphic to the graph in Figure 2.
Then G has a Hamilton cycle.
The conditions imply that [Fi_1, Fi] = 0,1 < i < N — 1, and hence there is a function, h, from a spanning subgraph of G to a path f0 f1 ■ ■ ■ fN_1 of length N — 1 defined by h(u) = fi for all u G Fi, 0 < i < N — 1.
In our next lemma, we adapt the result of Choo and MacGillivray to a more general scenario. Suppose G is a graph with vertex partition {F0, F1,..., FN_1} where G[Fi]
658
Ars Math. Contemp. 17 (2019) 493-514
Figure 2: Forbidden subgraph.
contains a spanning cycle for each i, 0 < i < N — 1 (these cycles form a 2-factor of G). Further, assume that there is a function, h, from a spanning subgraph of G to a tree with vertex set {f0, f1,..., fn-i} such that h(u) = fi for all u G Fi, 0 < i < N — 1. The general idea is to choose, for each edge fifj of the spanning tree, appropriate edges from the set [Fi; Fj ] of G so that we are able to construct a Hamilton cycle from among these edges and edges of the 2-factor. See Figure 3 for an illustration of this result.
Lemma 2.7. Let G be a graph with vertex partition {F0, F1y..., FN_i}, and let T be a tree with V (T) := {f0, fi,..., fN _i}. Suppose there is a function, h, from a spanning subgraph of G to T such that h(u) = fi for all u G Fi, 0 < i < N — 1. Furthermore, suppose that for each fifj G E (T), 0 < i,j < N — 1, there exist edges ei,j in G[Fi] and ej,i in G[Fj] such that
(i)	if j = k and fifj,fifk G E(T), then ei,j = ei,k;
(ii)	if ei,j = ac and ej,i = bd, then G[{a, b, c, d}] contains a 4-cycle;
(iii)	G[Fi] has a Hamilton cycle Ci such that
Proof. The proof is by induction on N. The result is trivial when N =1.
Let N > 1. For each fi fj G E(T), 0 < i < N — 1, suppose eij G E (G[Fi]), eji G E(G[Fj]), and Ci (a Hamilton cycle in G[Fi]) satisfy conditions (i), (ii) and (iii). Without loss of generality, we may assume that fN_1 is a leaf of T, and that fN_1fN_2 G E(T). Let G' := G — FN_1 and T' := T — fN_1. Using eitj, ej^ and Ci as previously defined, 0 < i < N — 2, and Mi as defined in (iii) except with MN_2 replaced by M'N_2 := Mn_2 \ {eN_2n_1}, we apply the induction hypothesis to G'. The result is a Hamilton cycle C' in G' such that
and eN_2,N_1 G E(C'). Let eN_2,N_1 := ac, eN_1,N_2 := bd; without loss of generality, abdca is a 4-cycle in G[{a, b, c, d}], and hence
Mi := {ei,j | fifj G E(T)} C E(Ci).
Then G has a Hamilton cycle C such that
N_1
lJ(E(Ci) \ Mi) C E(C).
i=0
C := (C' — eN_2,n_1) U (Cn_1 — eN_1,n_2) + {ab, cd}
is a Hamilton cycle in G with the required property.
□
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
659
We remark that if dT(/¿) = 1 for some i, then the Hamilton cycle C constructed in Lemma 2.7 contains all except one edge of E(Ci).
3 2-trees of diameter two
In this section we characterize 2-trees H of diameter two in which G4(H) has a Hamilton cycle. We begin by defining a class of 2-trees that we denote by T(p, q, r) (see Figure 4).
P
Q
Figure4: The 2-tree T(p, q, r).
Definition 3.1. Let P, Q, and R be pairwise disjoint independent sets of vertices with |P| := p, |Q| := q, and |R| := r. The graph T(p, q, r) is the graph onp + q + r + 3 vertices defined on vertex set {x, y, z} U P U Q U R where the subgraph induced by P U Q U R is an independent set, and
•	the subgraph induced by {x, y} U P is isomorphic to K1j1jP;
•	the subgraph induced by {y, z} U Q is isomorphic to K1j1jq;
•	the subgraph induced by {z, x} U R is isomorphic to K1,1,r.
A dominating vertex in a graph is a vertex adjacent to all other vertices of the graph.
660
Ars Math. Contemp. 17 (2019) 493-514
Lemma 3.2. A graph H is a 2-tree of diameter two if and only if H has a dominating vertex or H = T(p, q, r) for p, q, r > 0.
Proof. Any 2-tree with a dominating vertex has diameter two, and one can easily verify that T(p, q, r) is a 2-tree of diameter two for any p, q, r > 0.
For the converse, suppose H is a 2-tree of diameter two. We proceed by induction on n := |V(H)|. When n = 4, H is isomorphic to the graph obtained from K4 by deleting one edge, and has a dominating vertex. Now suppose that n > 5, and let u G V(H) be a leaf of H, i.e., (u) = 2. By the induction hypothesis, H - u has a dominating vertex, or H — u = T(p', q',r') for some p',q',r' > 0. If H — u = T(p', q',r') for some p', q', r' > 0, then let V(H — u) := {x, y, z} U P' U Q' U R', where |P'| := p', |Q'| := q', and |R'| := r'. Since H has diameter two, u must be adjacent to at least two vertices from {x, y, z}. However (u) = 2, and thus NH(u) = {x, y}, NH(u) = {y, z}, or NH(u) = {z, x}. It follows that H = T(p' + 1,q',r'), H = T(p',q' + 1,r'), or H = T (p', q', r' + 1), respectively.
Now suppose H — u has a dominating vertex, x. If ux G E(H), then x is a dominating vertex in H. Otherwise, let y and z denote the neighbours of u in H, and note that yz G E(H). Since H has diameter two, every vertex in V(H — u) is adjacent to x and at least one of y or z. Let P' be the set of vertices in H — u adjacent to both x and y, R' be the set of vertices in H — u adjacent to both x and z, and suppose |P'| := p' and |R'| := r'. Since H — u is a 2-tree, P' U R' is an independent set. Therefore, P' U R' U {u} is an independent set in H, and thus H = T (p', 1, r').	□
In what follows, we first prove that if p, q, r > 0, then G4(T(p, q, r)) has a Hamilton cycle. Let G be a graph with vertex partition {F0, Fi,..., FN_i}. For each i, 1 < i <
N — 1, let Si _i C Fi_i and Sj C Fj denote the vertices incident to the edges of [Fi-i, Fi].
Lemma 3.3. If p, q, r > 0, then G4(T(p, q, r)) has a Hamilton cycle.
Proof. Let V(K3) := {x, y, z}. Suppose /: V(K3) ^ {1, 2, 3,4} is a 4-colouring of K3 and V(G4(K3)) := {/0, f1,..., /N_1}. Since G4(K3) has a Hamilton cycle by [6, Theorem 4.1], we may assume that // • • • /N_1 is a Hamilton path in G4(K3).
For 0 < i < N — 1, let Fj be the set of 4-colourings of T(p, q, r) that agree with / on {x, y, z}. In order to simplify notation, we define G := G4(T(p, q, r)). Then {F0, F^ ..., Fn_1} is a partition of the vertices of G, and G[F^ = Qp+q+r, 0 < i < N — 1.
Let st G [Fi_1,Fi], where s G Si_1 and t G Sj for some 1 < i < N — 1. Then s(u) = t(u) for all u G V(G) \ {v}, where v is one of {x, y, z}, and s(v) = t(v). Thus, [Fi_1, Fj] is a set of independent edges. If v = x, then s(u) = s(w) for all u, w G P and for all u, w G R, and t(u) = t(w) for all u, w G P and for all u, w G R. Thus G[Si_1] = Qq ^ G[Sj], and G[Sj_i U Sj] = Q,+i. Analogously, if v = y, G[Sj_i] = Qr = G[Sj] and G[Sj_i U Sj] = Qr+i; and if v = z, G[Sj_i] = Qp = G[Sj], G[Sj_i U Sj] = Qp+i. Consider the path	in G4(K3), 1 < i < N — 2. Note that
/i_i(x),/i(x),/i+i(x)
use at most two different colours; otherwise, there would be only one colour available for y and z, which is impossible since y and z always receive different colours. Analogously, /i_1, /i, /i+1 assign at most two different colours to each of y and z. It follows that if
|[Fj_i,Fj]| = |[Fj, Fj+i]| = 2, then [Fi_l,Fi] U [Fi,Fi+l] = 2P3.
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
661
For each edge /¿-if with 1 < i < N - 1, we choose a 4-cycle, Bj_i, containing exactly two edges of [Fi-1, Fj] as follows.
•	For each |[Fj_i,Fj]| = 2, G[Sj_i U Sj] isa 2-cube, so we choose Bj_i := G[Sj_i U Sj] = ai_ici_idi6iai_i, where aj_i, cj_i G Fj_i and bj, dj G Fj.
•	For i = 1,2,..., N - 1, and |[Fj_i, Fj]| > 2, first note that |[Fj_i,Fj]| > 4 since G[Sj_i U Sj] = Qn for some n > 3. Thus it is possible to choose edges a^bj and cj_idj of [Fj_i, Fj] so that Bj_i := a^c^d.jbjaj_i is edge disjoint from Bj_2, and also edge disjoint from B, if | [Fj, Fj+1] | = 2 and i < N - 1.
Let eM+i := G[S^ n B, and ej+1jj := G[Sj+i] n B^ 0 < i < N - 2. Observe that G and the path /0/i • • • /N_i satisfy conditions (i) and (ii) of Lemma 2.7. Recall that G[Fj] = Qp+q+r, 0 < i < N -1, and p + q + r > 3. Since any pair of edges of Qn, n > 2, is contained in a Hamilton cycle (see [7, Theorem 4.1]), there exist Hamilton cycles C0 in G[F0] containing e0ji, CN_i in G[FN_i] containing eN_1jN_2, and, for 1 < i < N - 2, Gj in G[Fj] containing e^^ and ejjj+1. Therefore, by Lemma 2.7, G has a Hamilton cycle.	□
In the case where p > 0 and q = r = 0, T(p, q, r) has a dominating vertex, and is isomorphic to K2 V Kn.
Lemma 3.4. For n > 2, G4(K2 V Kn) has no Hamilton cycle.
Proof. Let H := K2 V Kn for n > 2, let H := G4(H), and let u, v be the two vertices of H of degree n + 1. For each 1 < i = j < 4 let
Vjj := {c G V(H) | c(u) = i and c(v) = j}.
Then
{V12, V13, Vi4, V21, V23, V24, V31, V32, V34, V41, V42, V43}
is a partition of V(H). Note that [Va^, V7a] = 0 if and only if a = 7 or ft = For 1 < i = j < 4, let Lj be an assignment of lists to the vertices of H such that Lj (u) := {i}, Ljj(v) := {j} and Ljj(x) := {1, 2,3,4} for x G V(H - {u,v}). Note that GLj (H) ^ H[Vjj] = Qn, for each 1 < i = j < 4. Define the three-coloured vertices of H (that is, the colourings of H with three colours) by c^ G Vj such that
i, if x = u, cjfc(x) := ^ j, if x = v, k, otherwise.
Each Vjj has two such vertices, cjjfcl and cjjfc2, where k1,k2 G {1, 2, 3,4}\{i,j}. Furthermore, H - {cjjkl, cjjfc2} is disconnected so that any Hamilton cycle in H must contain the edges of a Hamilton path of H[Vjj ] with endpoints cjj fcl and cjj fc2, for each 1 < i = j < 4.
By [6, Lemma 2.1] there is no Hamilton path in the n-dimensional cube from 00 • • • 0 to 11 • • • 1 whenever n is even. Thus, for n even, there is no Hamilton path in H[Vj ] with endpoints cjj fcl and cjj fc2. Therefore, H has no Hamilton cycle when n is even.
For n odd, such Hamilton paths exist and must be used in any Hamilton cycle of H, if one exists. We construct an auxiliary graph A (see Figure 5(a)) where the vertex (i, j)
662
Ars Math. Contemp. 17 (2019) 493-514
represents a Hamilton path in H[Vj] from cijkl to cijk2. There is an edge in A between
(i1,j1) and (i2,j2) whenever cilj1 k is adjacent to ci2j2k in H. We label the edge between (ii,ji) and (i2,j2) by the unique element of {1, 2,3,4} \ ({ii,ji} U {i2, j'2}) (see Figure 5(b)). Notice that the edges labelled i, 1 < i < 4, induce a 6-cycle, and the edges of these four 6-cycles partition E(A).
(1,4)
(3,4)
		3 4		
3 .. 4		4 4 1 1		1 ' 2
		1 2		
(a)
(b)
Figure 5: The auxiliary graph A.
3
2
3
A Hamilton cycle in H corresponds to a Hamilton cycle, C, in A in which any two consecutive edges of C have different labels. Such a cycle C uses a matching of size three from each labelled 6-cycle in A. Without loss of generality, we may assume C contains horizontal edges of the 6-cycle labelled 1. Now, C uses horizontal edges from one of the remaining labelled 6-cycles, otherwise, C contains a K3. Regardless of whether C uses horizontal edges of the 6-cycle labelled by 2, 3 or 4, using vertical edges of the two remaining 6-cycles gives C = C4 U C8, a contradiction. Therefore H has no Hamilton cycle.	□
Observe that if H is a 2-tree of diameter two having a dominating vertex u, then H =
T V {u} for some tree T.
Lemma 3.5. Let T be a tree on at least two vertices. Then G4(T V {u}) has a Hamilton cycle unless T is a star on at least three vertices or the bipartition of V (T) has two even parts.
The proof of this lemma requires a result that we state here, but whose proof is technical and is postponed to the Appendix A.
Lemma 3.6. Let T be a tree with bipartition (A, B), where |A| := £ and |B| := r, and let G3(T) be the 3-colouring graph of T with colours C = {1, 2,3}. Define cij to be the vertexof G3(T) with cij (a) = i for all a G A and cij (b) = j for all b G B.
(1)	If £,r > 0 are both even, then G3 (T) has no spanning subgraph consisting only of paths whose ends are in {c12, c13, c21,c23, c31, c32}.
(2)	If £ > 1 is odd and r > 0 is even, then G3(T) has a Hamilton path from c12 to c23.
(3)	If £ > 1 and r > 1 are both odd, then G3(T) has a Hamilton path from c12 to c13.
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
663
Proof of Lemma 3.5. Let T be a tree with | V (T) | > 2 and bipartition (A, B), where A := {xL, x2,..., x^} and B := {y1? y2, • • •, yr}• Let H := T V {u}, and let H := G4(H) be the 4-colouring graph of H with colours {1, 2,3,4}. For each 1 < k < 4, define
Vk := {c e V(H) | c(u) = k}.
Then {Vl, V2, V3, V4} is a partition of V (H). Define Lk to be an assignment of lists with
Lk(u) := {k} and Lk(w) := {1,2,3,4} for w e V(t). Note that GLfc (H) = H[Vk] = G3(T). Define the three-coloured vertices of H (that is, the colourings of H with three colours) by cijk e Vk so that cijk (x) := i for all x e A, cijk(y) := j for all y e B. Observe
[Vi, V2] = {c34ic342, c43ic432},	[Vi, V3] = {c24ic243, c42ic423},
[Vi, V4] = {c23ic234, c32ic324},	[V2, V3] = {ci42ci43, c4i2c4i3},
[V2, V4] = {ci32ci34, c3i2c3i4},	[V3, V4] = {ci23ci24, c2i3c2i4}.
Case 1. Suppose |V(T)| = 2. Then T V {u} = K3 and G4CK3) has a Hamilton cycle by [6, Theorem 4.1].
Case 2. Suppose T is a star with |V(T)| > 3. Then GftT V {u}) = K V Kn for some n > 2. By Lemma 3.4, G4(T V {u}) has no Hamilton cycle.
Case 3. Suppose both |A| and |B| are odd. By Lemma 3.6, there is a Hamilton path in H[Vi] from c42i to c43i, in H[V2] from c432 to ci32, in H[V3] from ci34 to ci24 and in H[V4] from ci23 to c423. The union of these paths with edges {c43ic432, ci32ci34, ci24ci23, c423 c42i} gives a Hamilton cycle in H.
Case 4. Suppose one of | A| and |B| is even and the other is odd. Without loss of generality, |A| is odd and |B| is even. By Lemma 3.6, there is a Hamilton path in H[Vi] from c23i to c34i, in H[Vi] from c342 to c4i2, in H[V3] from c4i3 to ci23 and in H[V4] from ci24 to c234. The union of these paths with edges {c34ic342, c4i2c4i3, c^cm, c234c23i} gives a Hamilton cycle in H.
Case 5. Suppose both |A| and |B| are even, and suppose H contains a Hamilton cycle C. Then C [Vi] is a spanning subgraph of H[Vi ] = G3 (T) consisting of a union of paths whose endpoints are three-coloured vertices of Vl, contradicting Lemma 3.6. Thus in this case, H has no Hamilton cycle.	□
4 Constructing 2-trees of diameter at least three
To complete the proof of our main result, we must show that if H' is a 2-tree with diameter at least three, then k0(H') =4. Naively deleting two leaves with the intention of applying Remark 2.6 may be problematic. For example, let H' be a 2-tree with diameter at least three having leaves x and y of distance at least three. Let H = H' - {x, y}, NH> (x) = {xL, x2}, and suppose G4(H) has a Hamilton cycle /0/l • • • fN_l/0. Let Fi be the set of 4-colourings of H' that agree with / on V(H), 0 < i < N - 1. In the case that fi_1/i arises from a colour change on xL and /i/i+1 arises from a colour change on x2, the subgraph G[Fj_ l U Fj U Fi+1] is isomorphic to the forbidden subgraph in Figure 2. Because of this we take a more general approach. Suppose a 2-tree H' is obtained from a 2-tree H by repeatedly adding vertices of degree two. Instead of a Hamilton cycle in G4(H) we take
664
Ars Math. Contemp. 17 (2019) 493-514
a spanning tree satisfying certain properties providing the flexibility needed to construct a Hamilton cycle in G4(H'). Our approach does not require G4(H) to have a Hamilton cycle. To facilitate this procedure, we define nine operations (see Figure 6).
Definition 4.1. Let H be a 2-tree. Then H' is obtained from H by
Operation I if {a,P,7} := V(H') \ V(H), {0,10,2, 6162, cic2} C E(H), and Nh'(a) = {01,02}, Nh>(P) = {61,62}, Nh>(7) = {01,02}.
Operation II if {a, P, 7} := V(H') \ V(H), {xo, x6, c1c2} C E(H), and NH, (a) = {x, o}, Nh'(P) = {x, 6}, Nh'(7) = {01,02}.
Operation III if {a,P,7} := V(H') \ V(H), {ox,xy,yc} C E(H), and NH(a) = {o,x}, Nh'(P) = {x, y}, Nh'(7) = {c,y}.
Operation IV if {a,P,7,5} := V(H') \ V(H), {xy, zw} C E(H), and NH (a) = Nh' (P) = {x, y}, Nh' (7) = Nh' (5) = {w,z}.
Operation V if {a,P,7,5} := V(H') \ V(H), {xy, zw} C E(H), and Nh' (a) = {P, x, y}, Nh' (P) = {a, y}, Nh' (7) = Nw (5) = {w,z}.
Operation VI if {a,P,7,5} := V(H') \ V(H), {xy, zw} C E(H), and NH (a) = {P, x, y}, Nh' (P) = {a, y}, Nh' (7) = {5, w, z}, Nh' (5) = {7, z}.
Operation VII if {a,P,7,5} := V(H') \ V(H), {xy,xz} C E(H), and NH' (a) = {P, x, y}, Nh' (P) = {a, y}, Nh' (7) = {5, x, z}, Nw (5) = {7, z}.
Operation VIII if {a,P,7,5} := V(H') \ V(H), {xy,xz} C E(H), and NH (a) = {P, x, y}, Nh' (P) = {x, a}, Nw (7) = {5, x, z}, Nh' (5) = {7, z}.
Operation IX if {a,P,7,5} := V(H') \ V(H), {xy,xz} C E(H), and NH (a) = {P, x, y}, Nh' (P) = {a, y}, Nh' (7) = Nw (5) = {x,z}.
Remark 4.2. Since each of Operations I through IX can be performed by sequentially adding simplicial vertices of degree two to H, H' is a 2-tree.
Recall that D denotes the unique 2-tree of diameter three on six vertices (Figure 1(a)).
Theorem 4.3. A graph H' is a 2-tree of diameter at least three if and only if H' = D or H' can be obtained from a 2-tree H by applying one of Operations I through IX.
Proof. (^): If H' = D, the result is trivially true. Otherwise, it follows from Remark 4.2 that H' is a 2-tree. Since each operation produces two leaves that are distance at least three apart, H' has diameter at least three.
(^): As already observed, D is the unique 2-tree of diameter three on six vertices. The 2-trees on three, four and five vertices all have diameter less than three. Thus, we may assume that H' is a 2-tree of diameter three and |V(H')| > 7. Since H' has diameter at least three, there are at least two leaves whose neighbourhoods are vertex disjoint. We consider cases based on the number of edges induced by the neighbourhoods of the leaves of H', and the number of leaves of H'.
Case 1. First assume that the neighbourhoods of the leaves of H' induce at least three distinct edges.
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
665
a
• ^ 02 bi -
?ß
Oi
Ci N / C2 \ / •7
(a) Operation I
ß «^a
z
.....»
x
7 • ^ 5
w
(d) Operation IV
ci
c2
;• 7
ß b
(b) Operation II
ß
^ y z
fx
I I I
a
7 •
5
xw (e) Operation V
y
a mC
*
O
>7
c
(c) Operation III
ß
f.
i i i
• ;
a
*
x
5 A
z
m" 1
i
7 w
(f) Operation VI
a
ß
O
x
2
y
a «- -
/ \ / \
ß*
x
•----¥y z¥-----*
ß5
(g) Operation VII
y z V----• ß	y
7
(h) Operation VIII
(i) Operation IX
Figure 6: Operations I through IX applied to a graph H by the addition of vertices a, fi, 7, and S where applicable. The solid edges belong to H and the dotted edges are added to construct H'.
5
x
7
x
a
7
a
z
If H' has three leaves whose neighbourhoods are pairwise vertex disjoint, then H' contains vertex disjoint edges a^, 6162, cic2, and leaves a, fi, 7 with N(a) = {ai; a2}, N(fi) = {61,62}, N(7) = {ci, C2}. Letting H := H' - {a, fi, 7} results in a 2-tree, and applying Operation I to H produces H'.
We may now assume that no three leaves of H' have neighbourhoods that are pairwise vertex disjoint. Choose two leaves a and 7 whose neighbourhoods are vertex disjoint, and
let fi £ {a, 7} be a leaf such that N(fi) £ {N(a), N(7)}. If N(fi) intersects exactly one of N(a) and N(7), then we may assume without loss of generality that |N(fi)nN(a) | = 1 and N(fi) n N(7) = 0. Then H' contains a path of length two, ax6 and an edge c1c2 that is vertex disjoint from ax6, such that N(a) = {a, x}, N(fi) = {x, 6}, and N(7) = {c1; c2}. Letting H := H' - {a, fi, 7} results in a 2-tree, and applying Operation II to H produces H'. Otherwise, |N(fi) n N(a)| = |N(fi) n N(7)| = 1, and H' contains a path of length three, c1xyc2 such that N(a) = {c1,x}, N(fi) = {x, y} and N(7) = {y, c2}. Letting H := H' - {a, fi, 7} results in a 2-tree, and applying Operation III to H produces H'.
Case 2. We may now assume that the neighbourhoods of the leaves of H' induce exactly two edges.
666
Ars Math. Contemp. 17 (2019) 493-514
Case 2(a). Suppose that H' has at least three leaves. Let leaves ft and 7 have neighbourhoods that are vertex disjoint, and let S G {ft, 7} be a leaf. Without loss of generality,
N (S) = N (7).
If there exists a leaf a with N(a) = N(ft), then H := H' - {a, ft, 7, S} is a 2-tree, and applying Operation IV to H produces H'. Otherwise, no other leaf of H' has the same neighbourhood as ft. If we let N(ft) := {a,y}, then at least one of {a,y} is a leaf of H' - ft; without loss of generality, a is a leaf of H' - ft, and so d(a) = 3. It follows that N(a) = {ft, y, x} for some x G {a, ft, 7, S, y}, and that xy G E(H').
Let N(7) = N(S) = {w, z}. We consider two cases depending on |{x} n {w, z}|. If |{x} n {w, z}| =0, then H := H' - {a, ft, 7, S} is a 2-tree, and applying Operation V to H produces H'. If |{x} n {w, z}| = 1, then y = w or y = z, and the two cases are analogous. The graph H := H' - {a, ft, 7, S} is a 2-tree, and applying Operation IX to H produces H'.
Case 2(b). Finally, assume that H' has exactly two leaves, ft and S, with N(ft) = {a, y} and N(S) = {7, z}. Since dH> (ft, S) > 3, {a, y} n {7, z} = 0. We may assume, without loss of generality, that a and 7 are leaves in H' - {ft, S}, and so d(a) = 3 and d(Y) = 3. It follows that N(a) = {ft, y,p} and N(7) = {S, z, q} for some p, q G {ft, a, S, 7} with p = y, q = z andpy, qz G E(H').
We consider three cases depending on |{p, y} n {q, z}|. If |{p, y} n {q, z}| = 0, then H := H' - {a, ft, 7, S} is a 2-tree, and applying Operation VI to H produces H'. If |{p, y} n {q, z}| = 1, then either p = q, p = z, or q = y. In the case p = q, H := H' - {a, ft, 7, S} is a 2-tree, and applying Operation VII to H produces H'. In the case p = z, H := H' - {a, ft, 7, S} is a 2-tree, and applying Operation VIII to H produces H'. The case q = y is analogous to the case p = z. Finally if |{p, y} n {q, z}| =2, then the fact that y = z implies that p = z and q = y, and hence H' = D, contradicting the fact that |V(H')| > 7.	□
5 Operations and the 4-colouring graph
Let H be a 2-tree, and let H' be the 2-tree obtained from H by applying one of the Operations I through IX. As before, let V(G^H)) := {fo, fb ..., fN-1}, and let Fj C V(G4(H')) be the set of 4-colourings of H' that agree with fj on the vertices of H, 0 < j < N - 1. For each Operation I through IX, what follows is a description of the subgraph of G := G4(H') induced by Fi, 0 < i < N - 1, and also a description of the subgraph of G induced by F U Fj when f G E(G4(H)), 0 < i, j < N - 1. Each edge fifj of G4(H) is also assigned a label to indicate the structure of G[Fi U Fj]. We remark that for a path ff fk of length two in G4(H), if fi(u) = fj (u) for some u G V(H), then fj(u) = fk(u).
5.1 Operation I
If H' is obtained from H using Operation I, then there are two choices of colour for each of the vertices a, ft, and 7, so for each i, 0 < i < N - 1, G[Fi] = Q3. To simplify the labelling of the vertices of G[Fi], we label the faces of a plane drawing of Q3 as shown in Figure 7(a), where a1 and a2 are the possible colours of vertex a, ft1 and ft2 are the possible colours of vertex ft, and y1 and y2 are the possible colours of vertex 7. Without loss of generality, assume these colour choices are as shown in Figure 7(b). A vertex u of
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
667
Q3 is assigned label «¿p Yk where i, j, k € {1,2}, and u is incident with the faces labelled Oj, Pj and jk (see Figure 7(c)).
«2
\	Yi	/
ßl	ai	ß2
7	Y2	
(a)
2
\	3	/
2	1	4
/		
223
224
(b)
Figure 7: Labelling G [Fi].
243
244
(c)
The following arguments can be made with sets of colours {/¿(ai), /¿(o^)}, j/i(bi), /j(62)} and {/i(c1), /¿(02)} each chosen independently as a subset of {1, 2,3,4}. To ease notation, we assume that /i(a1) = 3, /i(a2) = 4, /i(b1) = 1, /i(b2) = 3, /i(c1) = 1, and /i(c2) = 2. Then the colour choices for a are {1,2}, for fi are {2,4}, and for 7 are {3,4}. As already noted, G [Fi] = Q3; assume that G[Fi] has been drawn in the plane and labelled as in Figure 8(a).
If // G E(G4(H)), then /j is obtained from /i by changing the colour of a single vertex in V(H). We label each edge /i/j G E(G4(H)) according to the structure of
G[Fi u Fj].
(a)
2
2
2		
\	3	/
2	1	4
/		
(b)
(c)
2
\	3	f
3		(4
/		\
(d)
Figure 8: G [Fi] and G [Fi U Fj ] for Operation I, II and III.
(i) /i(v) = fj(v) for v € {ai, a2}. Without loss of generality, suppose v = ai. Since H is a 2-tree, there is a vertex a3 € V(H) such that H[{a1, a2, a3}] = K3. Observe /i(a3) € {1,2}; we may assume /¿(a3) = 1. Then /j(a1) = 2.1 Since /j(a2) =
1 Since fj (ai) is uniquely determined there is no fp with £ = j such that f and fp differ on ai.
668
Ars Math. Contemp. 17 (2019) 493-514
/¿(a^) = 4, the colours available for a are {1, 3}; the colours available for ft and Y are unchanged. Therefore [Fj, Fj ] is a matching of size four between the 4-cycle bounding the ai face in G[Fj] and the 4-cycle bounding either the ai face or the a2 face in G[Fj]. Thus G[Fj UFj] is isomorphic to the graph in Figure 8(b). We label the edge / /j by a-sq. It follows from Footnote 1 that there are at most two edges incident to / having label a-sq. Furthermore, we remark that if //, // G E(G4(H)) both have label a-sq, then the four vertices of Fj incident to the edges of [Fj, Fj ] are the same four vertices of Fj that are incident to the edges of [Fj, Fj2 ], and induce a 4-cycle in G[Fj] that bounds a face with label a1 or a2.
(ii)	/¿(v) = /j(v) for v G {b1,b2}. As in (i), we label the edge // by b-sq. Note that there are at most two edges incident to / having label b-sq. If //, // G E(G4(H)) both have label b-sq, then the four vertices of Fj incident to the edges of [Fj, Fj ] are the same four vertices of Fj that are incident to the edges of [Fj, Fj2 ], and induce a 4-cycle in G[Fj] that bounds a face with label or ,02.
(iii)	/¿(v) = /j(v) for v G {c1;c2}. As in (i) and (ii), we label the edge // by c-sq. Note that there are at most two edges incident to / having label c-sq. If /i/ji, /i/j2 G E(G4(H)) both have label c-sq, then the four vertices of Fj incident to the edges of [Fj, Fj ] are the same four vertices of Fj that are incident to the edges of [Fj, Fj], and induce a 4-cycle in G[Fj] that bounds a face with label y1 or y2.
(iv)	/j(u) = /j(u) for u G V(H) \ {a1; a2, b1, b2, c1; c2}. In this case, the vertex labels on G[Fj] and G[Fj] are identical. Thus [Fj , Fj-] is a perfect matching, and G[Fj U Fj] is isomorphic to the graph in Figure 8(c). We label the edge // by pm.
Table 1: Summary of Operation I.
Vertex whose colour is changed	Subgraph induced by Fj U Fj	Label of /¿/j
ai , a2	Figure 8(b)	a-sq
bi, 62	Figure 8(b)	b-sq
ci , c2	Figure 8(b)	c-sq
u G V(H) \ {ai, a2, bi, 62, ci, c2}	Figure 8(c)	pm
5.2 Operation II
As with Operation I, G[Fi] = Q3 for each i, 0 < i < N - 1. We may assume that /¿(a) = 4, /¿(x) = 3, /¿(6) = 1, /¿(ci) = 1, and /¿(c2) = 2. Then the colour choices for a are {1,2}, for ß are {2,4}, and for 7 are {3,4}. Using the same labelling convention as for Operation I, we assume that G[Fj] is drawn in the plane and labelled as in Figure 8(a).
If /¿/j G E(G4(H)), then / is obtained from / by changing the colour of a single vertex in V(H). We label each edge /¿/j G E(G4(H)) according to the structure of G[Fj U Fj].
(i) /¿(v) = /j(v) for v G {a, b, ci;c2}. This is analogous to Operation I when the colour of one of {ai; a2, bi, b2, ci; c2} is changed, and thus G[Fj U Fj] is isomorphic
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
669
to the graph in Figure 8(b). We label the edge f f by either a-sq, b-sq or c-sq as in Operation I.
(ii)	f (x) = f (x). We may assume that f (x) = 2. Then the colours available for a are {1,3} and the colours available for ß are {3,4}; the colours available for 7 are unchanged. Therefore, [Fj, Fj ] is a matching of size two where G[Fj] and G[Fj ] are edges whose endpoint labels are unchanged, and thus G[F U Fj ] is isomorphic to the graph in Figure 8(d). We label the edge f f by e.
(iii)	f (u) = f(u) for u € V(H) \ {a, b, x, ci, c2}. In this case, the vertex labels on G[Fj] and G[Fj] are identical. Thus [Fj, Fj] is a perfect matching, and G[Fi U Fj] is isomorphic to the graph in Figure 8(c). We label the edge f f by pm.
Table 2: Summary of Operation II.
Vertex whose colour is changed	Subgraph induced by Fi U Fj	Label of ff
a	Figure 8(b)	a-sq
b	Figure 8(b)	b-sq
C1 ,C2	Figure 8(b)	c-sq
x	Figure 8(d)	e
u G V(H) \ {a, b, x, ci, C2}	Figure 8(c)	pm
5.3 Operation III
As with Operations I and II, G[Fi] = Q3 for each i, 0 < i < N - 1. We may assume that /¿(x) = 3, / (y) = 1, /¿(a) = 4, and /¿(c) = 2. Then the colour choices for a are {1, 2}, for fi are {2,4}, and for 7 are {3,4}. Using the same labelling convention as for Operation I, we assume that G[Fj] is drawn in the plane and labelled as in Figure 8(a).
If /¿/j G E(G4(H)), then / is obtained from / by changing the colour of a single vertex in V(H). We label each edge // G E(G4(H)) according to the structure of G[F U Fj].
(i)	/¿(v) = /j (v) for v G {a, c}. This is analogous to Operation I when the colour is changed on one of {ai, a2, ci, c2}, and thus G[Fj U Fj] is isomorphic to the graph in Figure 8(b). We label the edge /j/j by either a-sq or c-sq as in Operation I.
(ii)	/¿(v) = /j (v) for v G {x,y}. This is analogous to Operation II when the colour of x is changed, and thus G[Fj U Fj ] is isomorphic to the graph in Figure 8(d). We label the edge /¿/j by e.
(iii)	/¿(u) = /j(u) for vertex u G V(H) \ {a, c, x, y}. In this case, the vertex labels on G[Fj] and G[Fj ] are identical. Thus [Fj, Fj ] is a perfect matching, and G F U Fj ] is isomorphic to the graph in Figure 8(c). We label the edge /¿/j by pm.
Remark 5.1. We note that for Operations I-III, if /¿/j,/¿/j2 G E(G4(H)) have the same label that is not e, and F/, F2 C Fj are incident to the edges of [Fj, Fj], [Fj, Fj2], respectively, then Fii = Fi2.
670
Ars Math. Contemp. 17 (2019) 493-514
Table 3: Summary of Operation III.
Vertex whose colour is changed	Subgraph induced by Fi U Fj	Label of fi fj
a	Figure 8(b)	a-sq
c	Figure 8(b)	c-sq
x, y	Figure 8(d)	e
u G V(H) \ {a, c, x, y}	Figure 8(c)	pm
5.4 Operation IV
We may assume that fi (x) = 1, fi (y) = 2, fi (w) = 2 and fi (z) = 3. Then the pairs of colour available for a and P, respectively, are
{(4,3), (3,3), (3,4), (4,4)},
and the pairs of colours available for 7 and S, respectively, are
{(1,4), (1,1), (4,1), (4,4)}.
Thus the subgraph of G induced by Fi is isomorphic to C4 □ C4, and we assume that it is drawn as shown in Figure 9(a), with the rows labelled by the pairs of colours available for a and P, respectively, and the columns labelled by the pairs of colours available for 7 and S, respectively.
If fi fj G E(G4(H)), then f is obtained from fi by changing the colour of a single vertex in V(H); there are three cases to consider.
(a)	(b)	(c)
Figure 9: G[F] and G[F U Fj] for Operation IV.
(d)
(i) fi(v) = fj (v) for v G {x,y}. We may assume that fj (x) = 4. Then the pairs of colours available for a and P, respectively, are
{(1,3), (3, 3), (3,1), (1,1)},
and the pairs of colours available for 7 and S are unchanged. Hence, G[Fi U Fj ] is isomorphic to the graph in Figure 9(b).
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
671
(ii)	/¿(v) = fj(v) for v e {w, z}. We may assume that fj(w) = 4. Then the pairs of colours available for 7 and respectively, are
{(2, 2), (2,1), (1,1), (1, 2)},
and the pairs of colours available for a and 3 are unchanged. Hence, G[F U Fj ] is isomorphic to the graph in Figure 9(c).
(iii)	/¿(u) = fj (u) for u e V(H) \ {x, y, w, z}. In this case, the vertex labels on G[Fj] and G[Fj] are identical. Thus [Fj,Fj] is a perfect matching, and G[Fj U Fj] is isomorphic to the graph in Figure 9(d).
Table 4: Summary of Operation IV.
	Subgraph induced by	
Vertex whose colour is changed	Fj U Fj	Label of /¿/j
x, y	Figure 9(b)	r
z, w	Figure 9(c)	c
u e V(H) \ {x, y, z, w}	Figure 9(d)	pm
Remark 5.2. We note that for Operation IV, if fj fj e E (G4(H)) has label r and e e [Fj, Fj], then each colouring corresponding to an end of e assigns the same colour to a and 3. Similarly, if fjfj e E(G4(H)) has label c and e e [Fj, Fj], then each colouring corresponding to an end of e assigns the same colour to 7 and
5.5 Operation V
We may assume that /¿(x) = 1, fj(y) = 2, /¿(w) = 2 and /¿(z) = 3. Then the pairs of colour available for a and 3, respectively, are
{(3,4), (3,1), (4,1), (4, 3)},
and the pairs of colours available for 7 and respectively, are
{(4,1), (1,1), (1, 4), (4,4)}.
Thus the subgraph of G4 (H') induced by Fj is isomorphic to P4 □ C4, and we assume that it is drawn as shown in Figure 10(a), with the rows labelled by the pairs of colours available for a and 3, respectively, and the columns labelled by the pairs of colours available for 7 and respectively.
If /¿fj e E(G4(H)), then fj is obtained from fj by changing the colour of a single vertex in V(H); there are five cases to consider. Since H is a 2-tree, there are vertices
a, b e V(H) such that H[{x, y, a}] = K3 and H[{w, z, b}] = K3. Observe /¿(a) e {3,4} and /¿(b) e {1,4}. We may assume that /¿(a) = 4 and fj(b) = 1. Even though b (respectively, a) could be equal to x or y (respectively, w or z), this does not affect the argument.
672
Ars Math. Contemp. 17 (2019) 493-514
(a)
(b)
(c)
(d)	(e)	(f)
Figure 10: Subgraphs induced by Fi U Fj for Operations V and IX.
(i)	fi (y) = fj (y). Then fj (y) = 3 and the pairs of colours available for a and f3, respectively, are
{(4,2), (4,1), (2,1), (2,4)},
and the pairs of colours available for 7 and 5 are unchanged. Hence, G[Fi U Fj ] is isomorphic to the graph in Figure 10(b) with appropriate labels.
(ii)	fi (x) = fj (x). Then fj (x) = 3 and the pairs of colours available for a and f3, respectively, are
{(4,1), (4,3), (1,3), (1,4)},
and the pairs of colours available for 7 and 5 are unchanged. Hence, G[Fi U Fj ] is isomorphic to the graph in Figure 10(c).
(iii)	fi (z) = fj (z). Then fj (z) = 4 and the pairs of colours available for 7 and 5, respectively, are
{(3,3), (1,3), (1,1), (3,1)},
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
673
and the pairs of colours available for a and ft are unchanged. Hence, G[Fi U Fj ] is isomorphic to the graph in Figure 10(d).
(iv)	fi(w) = fj(w). Then fj(w) = 4 and the pairs of colours available for y and S, respectively, are
{(3, 3), (1, 3), (1,1), (3,1)},
and the pairs of colours available for a and ft are unchanged. Hence, G[Fi U Fj ] is isomorphic to the graph in Figure 10(d).
(v)	fi(u) = fj(u) u G V(H) \ {x, y, w, z}. In this case, the vertex labels on G[Fi] and G[Fj] are identical. Thus [Fi; Fj] is a perfect matching, and G[Fi U Fj] is isomorphic to the graph in Figure 10(f).
Table 5: Summary of Operation V.
Vertex whose colour is changed	Subgraph induced by Fi U Fj	Label of fifj
y	Figure 10(b)	r
x	Figure 10(c)	rr
z, w	Figure 10(d)	c
u G V(H) \ {x, y, z, w}	Figure 10(f)	pm
We informally refer to the rows and columns of vertices in G[Fi] according to the drawing in Figure 10(a). For Operations IV and VI through IX we use a similar convention.
Remark 5.3. We note that for Operation V, if fifj G E(G4(H)) has label r, then the set of vertices Si j C Fi incident to the edges of [Fi; Fj] consists of row two or three2. If fifj G E(G4(H)) has label rr, then the set of vertices Sitj C Fi incident to the edges of [Fi; Fj] consists of rows one and two, or rows three and four. If fifj G E(G4(H)) has label c and e G [Fi; Fj], then each colouring corresponding to an end of e assigns the same colour to y and S.
5.6 Operation VI
We may assume that fi(x) = 1, fi(y) = 2, fi(z) = 3 and fi(w) = 1. Then the pairs of colour available for a and ft, respectively, are
{(3,4), (3,1), (4,1), (4, 3)},
and the pairs of colours available for y and S, respectively, are
{(2,4), (2,1), (4,1), (4, 2)}.
Thus G[Fi] is isomorphic to P4 □ P4, and we assume that it is drawn in the plane as shown in Figure 11(a), with the rows labelled by the pairs of colours available for a and ft, respectively, and the columns labelled by the pairs of colours available for y and S, respectively.
2 Rows are numbered from top to bottom and columns from left to right.
674
Ars Math. Contemp. 17 (2019) 493-514
(a)
(b)
(2,1) (2,4) (1,4) (1,2)
(e)
(c)
(3,2)(3,1)(2,1)(2,3) (d)
(f)
(2,1)(2,4)(1,4)(1,2) (g)
(2,1) (2,4) (1,4) (1,2) (h)
Figure 11: Subgraphs induced by Fi U Fj for Operations VI, VII and VIII.
If fifj G E(G4(H)), then fj is obtained from fi by changing the colour of a single vertex in V(H); there are five cases to consider. Since H is a 2-tree, there are vertices a, b G V (H) such that H [{x,y,a}] = K3 and H [{w,z,b}] = K3 .Observe fi (a) G {3,4} and fi(b) G {2, 4}. We may assume that fi(a) = 4 and fi(b) = 2. Even though b (respectively, a) could be equal to x or y (respectively, w or z), this does not affect the argument.
(i)	fi (y) = fj (y). Then fj (y) = 3, and the pairs of colours available for a and /, respectively, are
{(4,2), (4,1), (2,1), (2,4)},
and the pairs of colours available for 7 and 5 are unchanged. Hence, G[Fi U Fj ] is isomorphic the the graph in Figure 11(b).
(ii)	fi (x) = fj (x). Then fj (x) = 3, and the pairs of colours available for a and /, respectively, are
{(4,1), (4, 3), (1,3), (1,4)},
while the pairs of colours available for 7 and 5 are unchanged. Hence, G[Fi U Fj ] is isomorphic to the graph in Figure 11(c).
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
675
(iii)	/j(z) = / (z). Then / (z) = 4 and the pairs of colours available for 7 and respectively, are
{(3, 2), (3,1), (2,1), (2, 3)},
while the pairs of colours available for a and ft are unchanged. Hence, G[F U Fj ] is isomorphic the the graph in Figure 11(d).
(iv)	/(w) = /j (w). Then / (w) = 4 and the pairs of colours available for 7 and respectively, are
{(2,1), (2, 4), (1, 4), (1, 2)},
while the pairs of colours available for a and ft are unchanged. Hence, G[F U Fj ] is isomorphic the the graph in Figure 11(e).
(v)	/(u) = /j(u) for some u G V(H) \ {x, y, z, w}. In this case, the vertex labels on G[Fi] and G[Fj] are identical. Thus [Fi, Fj] is a perfect matching, and G[Fi U Fj] is isomorphic to the graph in Figure 11(f).
Table 6: Summary of Operation VI.
Vertex whose colour is changed	Subgraph induced by Fj U Fj	Label of /¿/j
y	Figure 11(b)	r
x	Figure 11(c)	rr
z	Figure 11(d)	c
w	Figure 11(e)	cc
u G V(H) \ {x, y, z, w}	Figure 11(f)	pm
Remark 5.4. We note that for Operation VI, if // G E(G4(H)) has label r (respectively, c), then the set of vertices C F incident to the edges of [Fj, Fj] consists of row (respectively, column) two or three. If /¿/j G E(G4(H)) has label rr (respectively, cc), then the set of vertices Sjj C Fj incident to the edges of [Fj, Fj ] consists of rows (respectively, columns) one and two or rows (respectively, columns) three and four.
5.7 Operation VII
We may assume that /¿(x) = 1, /¿(y) = 2 and /¿(z) = 3. Then the pairs of colours available for a and ß, respectively, are
{(3,4), (3,1), (4,1), (4, 3)},
and the pairs of colours available for 7 and J, respectively, are
{(2,4), (2,1), (4,1), (4, 2)}.
Thus G^] is isomorphic to P4 □ P4, and we assume that it is drawn in the plane as shown in Figure 11(a) with rows labelled by the pairs of colours available for a and ß, respectively, and the columns labelled by the pairs of colours available for 7 and J, respectively.
If /¿/j G E(G4(H)), then /j is obtained from / by changing the colour of a single vertex in V(H). There are four cases to consider.
676
Ars Math. Contemp. 17 (2019) 493-514
(i)	/¿(x) = fj (x). We may assume that /j (x) = 4. Then the pairs of colours available for a and ß, respectively, are
{(3,1), (3,4), (1, 4), (1, 3)},
and the pairs of colours available for 7 and respectively, are
{(2,1), (2,4), (1, 4), (1, 2)}.
Hence, G[F U Fj ] is isomorphic to the graph in Figure 11(g).
(ii)	/(y) = /j (y). This is analogous to Operation VI when the colour of y is changed, and thus G[F U Fj ] is isomorphic to the graph in Figure 11(b).
(iii)	/(z) = /j (z). This is analogous to Operation VI when the colour of z is changed, and thus G[Fi U Fj ] is isomorphic to the graph in Figure 11(d).
(iv)	/¿(u) = /j(u) for some u G V(H) \ {x,y, z}. In this case, the vertex labels on G[Fi] and G[Fj] are identical. Thus [F^ Fj] is a perfect matching, and G[Fj U Fj] is isomorphic to the graph in Figure 11(f).
Table 7: Summary of Operation VII.
Vertex whose colour is changed	Subgraph induced by Fj U Fj	Label of /
x	Figure 11(g)	sq
y	Figure 11(b)	r
z	Figure 11(d)	c
u G V(H) \{x,y,z}	Figure 11(f)	pm
Remark5.5. We note that for Operation VII, if // G E (G4(H)) has label r (respectively, c), then the set of vertices Sjj C Fj incident to the edges of [Fj,Fj] consists of row (respectively, column) two or three. If // G E(G4(H)) has label sq, then the set of vertices Sjj C Fj incident to the edges of [Fj, Fj] induces a four-cycle using a degree two vertex of G[Fj].
5.8 Operation VIII
We may assume that /j(x) = 1, /j(y) = 2 and /j(z) = 3. Then the pairs of colours available for a and ß, respectively, are
{(4, 3), (4, 2), (3, 2), (3,4)},
and the pairs of colours available for 7 and respectively, are
{(2,4), (2,1), (4,1), (4, 2)}.
Thus G[Fj] is isomorphic to P4 □ P4, and we assume that it is drawn in the plane as shown in Figure 11(a) with rows labelled by the pairs of colours available for a and ß, respectively,
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
677
and the columns labelled by the pairs of colours available for 7 and J, respectively (but not the same labels as in the figure).
If // € E(G4(H)), then / is obtained from / by changing the colour of a single vertex in V(H), and there are four cases.
(i)	/i(x) = /j (x). We may assume that / (x) = 4. Then the pairs of colours available for a and ß, respectively, are
{(1, 3), (1, 2), (3, 2), (3,1)},
and the pairs of colours available for 7 and J, respectively, are
{(2,1), (2, 4), (1, 4), (1, 2)}.
Hence, G[Fi U Fj] is isomorphic to the graph in Figure 11(h) with appropriate labels.
(ii)	/i(y) = /j (y). This is analogous to Operation VI when the colour of x is changed, and thus G[Fi U Fj ] is isomorphic to the graph in Figure 11(c) with appropriate labels.
(iii)	/i(z) = /j (z). This is analogous to Operation VI when the colour of z is changed, and thus G[Fi U Fj ] is isomorphic to the graph in Figure 11(d) with appropriate labels.
(iv)	/i(u) = /j(u) for some u € V(H) \ {x, y, z}. In this case, the vertex labels on G[Fi] and G[Fj ] are identical. Thus [Fi, Fj] is a perfect matching, and G[Fi U Fj ] is isomorphic to the graph in Figure 11(f).
Table 8: Summary of Operation VIII.
Vertex whose colour is changed	Subgraph induced by Fi U Fj	Label of //
x	Figure 11(h)	e
y	Figure 11(c)	rr
z	Figure 11(d)	c
u € V(H) \{x,y,z}	Figure 11(f)	pm
Remark 5.6. We note that for Operation VIII, if // G E(G4(H)) has label c, then the set of vertices Sftj C Fj incident to the edges of [Fi, Fj ] consists of column two or three. If /¿/j G E (G4(H)) has label rr, then the set of vertices Sjj C Fj incident to the edges of [Fj, Fj] consists of rows one and two or rows three and four. If // G E(G4 (H)) has label e, then the set of vertices Sjjj C Fj incident to the edges of [Fj; Fj] induces an edge that is the first or last edge of row two or row three.
5.9 Operation IX
We may assume that /¿(x) = 1, /j(y) = 2 and /¿(z) = 3. Then the pairs of colours available for a and ft, respectively, are
{(4, 3), (4,1), (3,1), (3,4)},
678
Ars Math. Contemp. 17 (2019) 493-514
and the pairs of colours available for 7 and J, respectively, are
{(2, 2), (2,4), (4, 4), (4, 2)}.
Thus G[Fi] is isomorphic to P4 □ C4, and we assume that it is drawn in the plane as shown in Figure 10(a) with rows labelled by the pairs of colours available for a and ß, respectively, and the columns labelled by the pairs of colours available for 7 and J, respectively (but not the same labels as in the figure).
If fifj € E(G4(H)), then fj is obtained from f by changing the colour of a single vertex in V(H); there are four cases.
(i)	fj(x) = fj (x). We may assume that fj (x) = 4. Then the pairs of colours available for a and ß, respectively, are
{(3,1), (3,4), (1, 4), (1, 3)},
and the pairs of colours available for 7 and J, respectively, are
{(2,1), (2, 2), (1, 2), (1,1)}.
Hence, G[F U Fj] is isomorphic to the graph in Figure 10(e) with appropriate labels.
(ii)	fj(y) = fj (y). This is analogous to Operation V when the colour of y is changed, and thus G[Fj U Fj ] is isomorphic to the graph in Figure 10(b) with appropriate labels.
(iii)	fi(z) = fj (z). This is analogous to Operation V when the colour of z is changed, and thus G[Fj U Fj ] is isomorphic to the graph in Figure 10(d) with appropriate labels.
(iv)	fi(u) = fj(u) for some u € V(H) \ {x,y, z}. In this case, the vertex labels on G[Fj] and G[Fj] are identical. Thus [Fj, Fj] is a perfect matching, and G[Fj U Fj] is isomorphic to the graph in Figure 10(f).
Table 9: Summary of Operation IX.
Vertex whose colour is changed	Subgraph induced by Fj U Fj	Label of fjfj
x	Figure 10(e)	e
y	Figure 10(b)	r
z	Figure 10(d)	c
u € V(H) \{x,y,z}	Figure 10(f)	pm
Remark 5.7. We note that for Operation IX, if // G E(G4(H)) has label r and e G [Fj, Fj], then each colouring corresponding to an end of e assigns the same colour to a and p. Similarly, if // G E(G4(H)) has label c and e G [Fj, Fj], then each colouring corresponding to an end of e assigns the same colour to 7 and J. If //j G E(G4(H)) has label e and e G [Fj, Fj], then the set of vertices Sjj C Fj incident to the edges of [Fj, Fj] induces an edge that is either the first or last edge in a column, and each colouring corresponding to an end of e assigns the same colour to 7 and J.
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
679
6 4-colouring graphs of 2-trees of diameter at least three
Let H be a 2-tree, and let H' be a 2-tree obtained from H by applying one of the Operations I through IX. We prove G4(H') has a Hamilton cycle.
6.1 Operations I, II and III
We first prove a result about Hamilton cycles in a cube Q3 that will later be used to show the existence of edges satisfying Lemma 2.7. In this section, we let each face label in Figure 12(a) denote the 4-cycle bounding that face.
h4
(a)	(b)
Figure 12: Labelling G[Fi]. We label the six Hamilton cycles of a plane drawing of Q3 as shown in Figure 13.
@010@l
(a) C	(b) n	(c) □	(d) U	(e) H	(f) I
Figure 13: Labels for the Hamilton cycles of Q3.
To simplify notation for multisets, we write nZ to mean n copies of Z.
Lemma 6.1. Let Q = Q3 be drawn as in Figure 12(a), and let e be an edge of Q. Let Z = {Z1 ,Z2,..., Zn} be a multiset such that Z C {2a1, 2^1, 2^1,5Q3} and n < 5. That is, each Zi is an induced subgraph of Q and is either the entire 3-cube or one of the 4-cycles of Q labelled by a1, or y1. Then there exists a Hamilton cycle in Q containing distinct edges {e, e1, e2,..., en} such that ei G E (Zi),for 1 < i < n.
Proof. It is enough to prove the result when n = 5 and Z = {2a1; 2p1, y1}. Note that the Hamilton cycles U and n in Q each contain three edges of a1, three edges of p1, and two edges of y1 . When any single edge is deleted from U or n, we see that the resulting Hamilton path contains five distinct edges, two from a1, two from p1 and one from j1. Since at least one of U and n contains the edge e, either U or n contains distinct edges {e, e1, e2,..., e5} such that ei G E(Zi), for 1 < i < 5.	□
680
Ars Math. Contemp. 17 (2019) 493-514
Lemma 6.2. Let Q = Q3 be drawn as in Figure 12(a) with edges labelled as in Figure 12(b). Assume {e, e'} C E(Q) with e e {wi, w2, w3, w4}. Let Z = {Zi, Z2,..., Zn} be a multiset such that Z C {a1,31, 2y1, 4Q3} and n < 4. That is, each Zj is an induced subgraph of Q and is either the entire 3-cube or one of the 4-cycles of Q labelled by a1, 31, or y1. Then there exists a Hamilton cycle in Q containing distinct edges {e, e', e1, e2,..., en} such that ej e E(Zj),for 1 < i < n.
Proof. It is enough to prove the result when n = 4 and Z = {a1,31, 2y1 } with Z1 := a1, Z2 := ^1, Z3 := 71 and Z4 := 71. Let H := {h-1, h-2, h3, h.4}, W := {w1, w2, w3, w4} and D := {d1, d2, d3, d4}. For each Zj, we designate a set of candidate edges for ej as follows (see Table 10).
Table 10: Cases in the proof of Lemma 6.2.
	Cycle	Edges et assigned to Zi			
e', e	in Q	Zi	Z2	Z3	Z4
e' e H, e e {wi, w2}	c	{h2,h3}\{e'}	{wi,w2} \ {e}	d2	{hi,h2}\{e'}
e' e H, e e {w3, w4 }	□	{h2,h3}\{e'}	d4	di	{hi,h2}\{e'}
{e, e'} = {wi, W2}	n	W3	d4	hi	h2
e,e' e W, {e,e'} = {w1,w2}	u	h3	{wi, W2} \ {e, e'}	di	d2
e' e D, e e {w1, w4}	H	h3	{di ,d4}\{e'}	hi	{di,d2}\{e'}
e' e D, e e {w2, W3}	I	{w2, W3} \ {e}	{di ,d4}\{e'}	hi	{di,d2}\{e'}
As indicated in Table 10, the first case has e' e H and e e {w1, w2}. We claim that C has the required property. We take e3 := d2, and as |{w1, w2} \ {e}| = 1, we take {e2} := {w1, w2} \ {e}. Observe that the sets {h2, h3} \ {e'} and {h1, h2} \ {e'} are distinct and non-empty. Thus, we may take e1 e {h2, h3} \ {e'} and e4 e {h1, h2} \ {e'} so that e1 = e4. The remaining five cases follow using analogous arguments.	□
Lemma 6.3. Suppose H' is obtained from a 2-tree H by applying one of Operations I, II or III. Then G4(H') has a Hamilton cycle.
Proof. Case 1. Suppose H' is obtained from H by applying Operation I. By Lemma 2.5, G4(H) has a spanning tree T with A(T) < 4. Let V(T) := {fo, /1,..., /n-1} such that fo is a leaf, and root T at f0, turning T into a branching, —, by directing all arcs away from fo.
Let G := G4(H'), and let Fj be the set of 4-colourings of H' that agree with fj on V (G4(H)), 0 < i < N -1. Label each -fj e A(—) with the label of /¿fj e E (G4(H)), as described in Section 5, and let Sj,j C Fj denote the vertices incident to the edges
of [Fj, Fj].
For each arc —/j e ), we choose edges ej,j in G[Fj] and ej,j in G[Fj] satisfying conditions (i) and (ii) of Lemma 2.7 as follows. Suppose —0/1 e A(——). The fact that G[F0 U F1] is isomorphic to the graph in Figure 8(b) or 8(c) gives us the flexibility to choose e0j1 e E(G[F0]) and e1j0 e E(G[F1 ]) satisfying (ii) of Lemma 2.7.
Edge choosing procedure. Now suppose for some i, ej k has been chosen in G[Fj] but ej j has not yet been chosen for each j where — fj e A(—). For this i, let J := {j |
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
681
—/j G A(T)}. We choose edges e^j and j for j g J as follows. Assume that G[F'] is drawn as in Figure 12(a). By Remark 5.1, S. = S^j whenever // and /¿j have the same label. Without loss of generality, we may assume that an arc // with label a-sq has G^j] isomorphic to the 4-cycle a1, an arc // with label b-sq has G^.] isomorphic to the 4-cycle and an arc /'/j with label c-sq has G^.] isomorphic to the 4-cycle y1. For each j G J, let Zj := G^.], and define the multiset Z := {Zj | j G J}. Then each Zj is either a 3-cube or one of the 4-cycles a1, or y1. Since / is incident to at most two edges with label a-sq, at most two edges with label b-sq, and at most two edges with label c-sq, Z C {2ai, 2£i, 27i, 5Q3}. Observe |Z| < 4 since A(T) < 4. By Lemma 6.1, using e := ejjfc, there is a Hamilton cycle Q in G[F'] and an edge e^j G E(Zj) for each Zj G Z such that e. = e. whenever j = j2. Thus (i) of Lemma 2.7 is satisfied. Furthermore, for each j G J there is an edge e.^ G E(G[Fj]) such that e^j and e^ satisfy (ii) of Lemma 2.7.
Now suppose for every — /j G A(T), e^j and e^ have been chosen as above. By construction, (i) and (ii) of Lemma 2.7 are satisfied, and for each G[F'], 0 < i < N — 1, the Hamilton cycle Q satisfies condition (iii) of Lemma 2.7. Therefore, G has a Hamilton cycle.
Case 2. Suppose H' is obtained from H by applying Operation II. Let H := G4(H) and V (H) := {/o,/i,.. .,/n _i}. For each 1 < i < 4 let Vj := {c G V (H) | c(x) = i}. Then {V1, V2, V3, V4} is a partition of V(H). Let Lj be an assignment of lists with Lj(x) := {i} and Lj(w) := {1,2,3,4} for w G V(H) \ {x}. Note that GLi(H) = H[Vj] and that H[Vi] = H[V2] = H[V3] = H[V4]. Thus, H can be partitioned into four copies isomorphic to GLl (H) with edges between pairs of copies. Furthermore, each edge in E(H[Vj]), 1 < i < 4, has label a-sq, b-sq, c-sq or pm, and each edge with one endpoint in Vj and the other endpoint in Vj, i = j, has label e.
By Lemma 2.5, H[Vj], 1 < i < 4, has a spanning tree Tj with A(Tj) < 4. Note that [Vj, Vj] = 0 for 1 < i = j < 4. Choose one edge from each of [Vi, V2], [V2, V3], and [V3, V4]. Without loss of generality, suppose the chosen edges are /i/2 G [Vi, V2], /2/3 G [V2, V3], and /3/4 G [V3, V4] such that /j G Vj, 1 < i < 4. Since // /2/3 and /3 /4 each have label e in H and each vertex of V (H) is incident to at most one edge with label e, the vertices /i, /2, /2, /3, /¿j, /4 are distinct. Thus, we may assume that /2 = /0 and /3 = /5.
Let T be the spanning tree of H consisting of the union of T\, T2, T3, T4, and the edges {/i/2, /0/3, /5/4}. Then A(T) < 5 and the only edges of T with label e are // /0/3 and /4/5. Root T at /i, turning T into a branching, T, by directing all arcs away from /i. This gives a branching Tj for each Tj, 1 < i < 4, and by our choice of labels, /j is the root of Tj.
Let G := G4(H'), and let Fj be the set of 4-colourings of H' that agree with /j on
V(G4(H)), 0 < i < N — 1. Label each — j g A(T) with the label of / G E(H), and let Sj,j C Fj and Sj C Fj denote the vertices incident to the edges of [Fj, Fj ].
For each arc —/j G A(T), we choose edges ej,j in G[Fj] and ej,j in G[Fj] satisfying conditions (i) and (ii) of Lemma 2.7 as follows. For (i, j) G {(1,2), (0,3), (5,4)} (where /j/j has label e), let ej,j be the unique edge of G[Sj,j] C G[Fj] and ej,j be the unique edge of G[Sj] C G[Fj]. For — and T—4 we apply the edge choosing procedure used in Case 1,
682
Ars Math. Contemp. 17 (2019) 493-514
starting with with ei,2 in G[F\] for Ti, and e4,5 in G[F4] for if. The resulting set of edges
Rj, ej,i | / e (A(it U it) U {/lif, ^/t})}
and set of cycles {Gj | / e Vi U V4} satisfy Lemma 2.7. For if, we let /M be the parent of /0 and /k the parent of /M. Let if' be the subtree of if obtained by deleting the descendants of /M and T2" be the subtree of if rooted at /m . If M = 2 then k = 1, so eM k = e21. Otherwise apply the apply the edge choosing procedure used in Case 1 to if', starting with e21 in G[F2]. This leads to the designation of an edge eM,k in G[FM ].
Let J := {j | e A(if)}. We choose edges eM,j and ejjM for j e J as follows. Without loss of generality, we may assume that an arc /M/ with label a-sq has G[SMjj] isomorphic to the 4-cycle a1, an arc /M/ with label b-sq has G[SM j] isomorphic to the 4-cycle an arc /M /j with label c-sq has G[SM j ] isomorphic to the 4-cycle y1, and an arc with label pm has G[SMjj] isomorphic to Q3. Let Z be a multiset consisting of the graphs Zj := G[SM,j ] for j e J.
Suppose there exists I e (J \ {0}) such that both /M/0 and /M/ have label c-sq. We apply the edge choosing procedure used in Case 1 to if'', with chosen edge eM,k. The resulting set of edges {eM,j | j e J} and cycle CM satisfy Lemma 2.7. Observe that eM,0, eMj£ e E(71). Suppose eM,0 = ab, and let the vertices of [{a, b}, F0] incident to F0 be {c, d}. If e0 3 = cd then exchange eM 0 with eM i. It now follows that for each j e J there is an edge ejjM e E(G[Fj]) such that eM,j and ejjM satisfy (ii) of Lemma 2.7, with eo,M = eo,3.
Otherwise /M /0 is the only arc in {/M /j | j e J} labelled c-sq, or /M /0 has label a-sq, b-sq, or pm. To ensure (i) of Lemma 2.7 is satisfied for i = 0, we duplicate Z0 e Z and apply Lemma 6.1. Let Z0 := Z0 and F0/ := F0. Observe |Z U {Z0/}| < 5 since A(T) < 4. Since /M is incident to at most one edge with label a-sq, at most one edge with label b-sq, and at most two edges with label c-sq, (Z U {Z0/}) C {2a1; 2^1; 271, 5Q3}. By Lemma 6.1 applied to Z U {Z0/}, and using e := eM,k, there is a Hamilton cycle CM in G[Fm] and edges eM,j e E(Zj) for each j e (J U {0'}) such that eM,j1 = eM,j2 whenever j = j2. Thus (i) of Lemma 2.7 is satisfied for i = M. Furthermore, for each j e (J U {0'}) there is an edge ejjM e E(G[Fj]) such that ejjM and eM,j satisfy (ii) of Lemma 2.7. Since eMj0/ = eM,0, we have e0,M = e0/,M, and hence, one of e0,M and e0/jM is different from e0,3. If e0,M = e0,3 then we ignore e0/,M and eMj0/; otherwise, redefine e0,M to be e0',M and eM,0 to be eMj0' so that (i) of Lemma 2.7 is satisfied for i = 0.
Finally, let G[F0] = Q3 be drawn as in Figure 12(a) with edges labelled as in Figure 12(b). Observe that e = e0,3 e {w1; w2, w3, w4} and let e' := e0,M. Let J := {j | Zofj e A(ff)}. We choose edges e0,j and ejj0 for j e J as follows. Without loss of generality, we may assume that an arc /0/j with label a-sq has G[S0jj] isomorphic to the 4-cycle a1, an arc /0/j with label b-sq has G[S0jj] isomorphic to the 4-cycle an arc /0/j with label c-sq has G[S0jj ] isomorphic to the 4-cycle 71, and an arc with label pm has G[S0,j] isomorphic to Q3. Let Z be a multiset consisting of the graphs Zj := G[S0jj] for j e J. Observe Z C {a1; 271, 4Q3} and |Z| < 4. By Lemma 6.2, there exists a Hamilton cycle C0 in G[F0] containing distinct edges {e, e'} U {e0 j | j e J} such that
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
683
e0,j £ E(Zj) for j £ J. Thus (i) of Lemma 2.7 is satisfied for i = 0. Furthermore, for each j £ J there is an edge ej,0 £ E (G[Fj ]) so that ej,0 and e0,j satisfy (ii) of Lemma 2.7.
We now apply the edge choosing procedure used in Case 1 to the remaining nodes o f -2. This designates edges e^ in G[Fi] and e.^ in G[Fj], and cycles Gj satisfying Lemma 2.7. For - we apply the argument for T2 giving us edges e^- in G[Fj] and e^ in G[Fj], and cycles Gj satisfying Lemma 2.7, for each -fj £ A(t3).
Now ej,j and e.^ have been chosen for all -fj £ A(-). By construction, each such ej,j and e^ satisfy (ii) of Lemma 2.7, and for each G[Fj], 0 < i < N - 1, the Hamilton cycle Gj satisfies condition (iii) of Lemma 2.7. Furthermore, the collection of chosen edges are all distinct. Therefore, G has a Hamilton cycle.
Case 3. Suppose H' is obtained from H by applying Operation III. Let H := G4(H) and V(H) := {fo, f1,..., fN-1}. For each 1 < i = j < 4 let
Vj := {c £ V(H) | c(x) = i and c(y) = j}.
Then
V := {V12, V13, V14, V21, V23, V24, V31, V32, V34, V41, V42, V43}
is a partition of V(H). Note that [Va|g, V7a] = 0 if and only if a = 7 or fi = S. Furthermore, each edge in E(H[Vjj]), 1 < i = j < 4, has label a-sq, c-sq or pm, and each edge with one endpoint in Vjj and the other endpoint in Vj2j2, (i1,j1) = (i2,j2), has label e. Let {i, j, k} C {1, 2, 3,4}. As H is a 2-tree, H is 3-colourable and for each 1 <
i = j < 4, there is a unique vertex cjjk £ V(H) with cjjk (x) = i, cjjk (y) = j and cjjfc(w) £ {i, j, k} for w £ V(H) \ {x,y}. Consider the ordering
(V14, V12, V32, V34, V31, V21, V24, V23, V13, V43, V42, V41)
of V. For each Vj £ V \ {V41}, suppose immediately follows VjJ- in the list. Then |{i,j} u {^,m}| = 3, and hence there is a unique kjj £ {1, 2, 3,4} \ ({i,j }U{^,m}) such that cjjkij £ Vjj. The ordering of V ensures that for each Vjj £ V \ {V42, V41} with immediately following Vjj in the list, kjj = k^m. Choose the edge c14c'14 from [V14, V12] with endpoint c14 := c143 £ V14; note that c'14 = c124. For each [Vjj, V^m] where Vim immediately follows Vjj in the list, there is a unique edge cjJ cj^ with endpoint cij = cjjfcij £ ^ij.
By Lemma 2.5, H[Vj], 1 < i = j < 4, has a spanning tree Tj with A(Tjj-) < 4. Let T be the spanning tree of H with Tjj C T, 1 < i = j < 4, and cjjcj^ £ E(T), 1 < i = j < 4 with (i, j) = (4,1). Then A(T) < 5 and the only edges of T with label
e are cjjcjj, 1 < i = j < 4 with (i, j) = (4,1). Root T at c143 £ V14, turning T into a
branching, T, by directing all arcs away from c14. This gives a branching i-jj for each TjJ, 1 < i = j < 4. Now repeat the argument in Case 2 for each Tjj, 1 < i = j < 4.	□
6.2 Operations IV to IX
We introduce some labelled Hamilton cycles of C4 □ C4, P4 □ C4 and P4 □ P4 to be used in Lemma 2.7 to show the existence of a Hamilton cycle in G4(H'), where H' is obtained from a 2-tree H by applying one of Operations IV through IX.
684
Ars Math. Contemp. 17 (2019) 493-514
Let □ be the edge labelled Hamilton cycle in C4 □ C4 shown in Figure 14, with the edges in rows two and four labelled by r, the edges in columns two and four labelled by c, and the remaining edges left unlabelled. Let C and C' be the edge labelled Hamilton cycles in P4 □ C4 shown in Figure 14, and let 1, 1' and 1'' be the edge labelled Hamilton cycles in P4 □ P4 shown in Figure 14.
(a)H
(b) C
(c) C'
(d) 1	(e) I'	(f) l"
Figure 14: Labelled Hamilton cycles of C4 □ C4, P4 □ C4 and P4 □ P4.
Lemma 6.4. Suppose H' is obtained from a 2-tree H by applying one of Operations IV through IX. Then G4 (H') has a Hamilton cycle.
Proof. By Lemma 2.5, H := G4(H) has a spanning tree T with A(T) < 4. Let V(T) := {f0, f1, • • •, fN-1} such that f0 is a leaf, and root T at f0, turning T into a branching, —, by directing all arcs away from f0. Let G := G4 (H'), and let Fi be the set of 4-colourings of H' that agree with fi on V(H), 0 < i < N - 1. Label each f G A(7?) with the label of fi fj G E (H), and let Si j C Fj and Sj C Fj denote the vertices incident to the edges
of [Fi, Fj ].
We first traverse T using breadth-first search starting at f0 to construct a drawing of each G[Fj] as shown in Figure 9(a) for Operation IV, Figure 10(a) for Operations V and IX, and Figure 11(a) for Operations VI, VII and VIII, so that each drawing has the following property, denoted (*).
(*) The rows are labelled by the pairs of colours available for a and P, respectively, and the columns are labelled by the pairs of colours available for 7 and S, respectively. In the case of Operations IV, V and IX, we further assume that the second and fourth columns have 7 and S the same colour. Also, in the case of Operation IV, we assume the second and fourth rows have a and P the same colour.
Start with a drawing of G[F0] satisfying (*). Assume —/j G ) where G[Fj] has been drawn but G[Fj ] has not. We draw G[Fj ] satisfying (*) as follows. If fi fj has label
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
685
•	pm, then draw G[Fj ] so that the labels of the rows and columns are in the same order
as in G[Fjj.
•	r, then draw G[Fj] so that the column labels of G[Fj] are in the same order as the column labels of G[Fj], and so that the row number of Sj in G[Fj ] is the same as that of Sij in G[Fj]. This can be done for Operation IV due to the cyclic structure of C4 □ C4; furthermore, (*) guarantees that Sij and S' have row number two or four. For Operations V, VI, VII and IX, this can be done by Remarks 5.3, 5.4, 5.5 and 5.7. Thus, one of the two possible labellings for the rows of G[Fj] gives a drawing of G[Fj ] such that the row number of Sj in G[Fj ] is the same as that of Sij in G[Fi].
•	c, then draw G[Fj ] so that the row labels of G[Fj ] are in the same order as the row labels of G[Fi], and so that the column number of Sj in G[Fj ] is the same as that of Sij in G[Fi]. This can always be done using a similar argument as in the case for fifj having label r. For Operations IV, V and IX, (*) guarantees that Sij and S' have column number two or four. For Operations VI, VII and VIII, by Remarks 5.4, 5.5 and 5.6, Sij and Sj have column number two or three.
•	rr, then draw G[Fj ] so that the column labels of G[Fj ] are in the same order as the column labels of G[Fi], and so that the set of row numbers of Sj in G[Fj ] is the same as that of Sij in G[Fi]. This can be done for Operations V, VI and VIII, since by Remarks 5.3, 5.4 and 5.6, the set of row numbers of Sij and S' is either {1,2}
or {3,4}.
•	cc, then draw G[Fj ] so that the row labels of G[Fj ] are in the same order as the row labels of G[Fi], and so that the set of column numbers of S' in G[Fj ] is the same as that of Sij in G[Fi]. This can be done for Operation VI, since by Remark 5.4, the set of column numbers of Sij and S' is either {1, 2} or {3,4}.
•	sq, then draw G[Fj] satisfying (*).
•	e, then draw G[Fj ] satisfying (*). Note that for Operation IX, (*) guarantees that Sij and Sj' belong to column number two or four.
For Operation IV (respectively, V, VI, VII, VIII, and IX), for each i, 0 < i < N - 1, let Ci be the Hamilton cycle □ (respectively, c, I, I', I'', and c') in G[Fi].
We describe how to construct a set of edges
E := {eij,ej,i | fifj G E(T)}
so that for each arc — fj G A(—), the edges ei,j in G[Fi] and ej- in G[Fj] satisfy conditions (i) and (ii) of Lemma 2.7, and so that eij G E (Ci) and ej- G E (Cj ). Start with E := 0. We consider the arcs of7? in the following order according to their labels.
(1) For each ——^ G A{jÎ) with label e (Operations VIII and IX), eij G G[Fi] and ej- G G[Fj ] satisfying condition (ii) of Lemma 2.7 are uniquely determined. Note that for Operation VIII, eij G Ci and has label e, and ej- G Cj and has label e; this follows by the symmetry of I'' and the drawings G[Fi] and G[Fj]. For Operation IX, eij G Ci and has label c/e, and ej- G Cj and has label c/e; this follows from the drawings of G[Fi] and G[Fj], and Remark 5.7. Add eijj and ej- to E.
686	Ars Math. Contemp. 17 (2019) 493-514
(2)	For each —fj G A(—) with label sq (Operation VII), choose e^j in Ci with label sq and e^ in G[Fj] satisfying condition (ii) of Lemma 2.7. Note that e^ G Cj and has label sq or label r/sq; this follows from the drawings of G[Fi] and G[Fj], and Remark 5.7. Add eiij and ejii to E.
(3)	For each —fj G A(—) with label rr (Operations V, VI and VIII), choose eiij in Ci with label rr and ejii in G[Fj] satisfying condition (ii) of Lemma 2.7. Note that eji G Cj and has label rr; this follows from the drawings of G[Fi] and G[Fj]. Add ei,j and ej,i to E.
(4)	For each — fj G A(—) with label cc (Operation VI), choose ei,j in Ci with label cc and eji in G[Fj ] satisfying condition (ii) of Lemma 2.7. Note that ejii G Cj and has label cc; this follows from the drawings of G[Fi] and G[Fj]. Add ei,j and ej,i to E.
(5)	For each — fj G A(—) with label r (Operations V, VI and IX), choose ei,j in Ci with label r and ej,i in G[Fj] satisfying condition (ii) of Lemma 2.7. Note that ej,i G Cj and has label r; this follows by the drawings of G[Fi] and G[Fj]. Add ei,j and ej,i to E.
For each —fj G A(—) with label r (Operation VII), choose ei,j in E(Ci) \ E with label r/sq and ej,i in G[Fj] satisfying condition (ii) of Lemma 2.7. This is possible since I' has four edges with label r/sq. Note that ej,i g Cj and has label r/sq; this follows by the drawings of G[Fi] and G[Fj]. Add ei,j and ej,i to E.
In the context of Operation IV, let T' be the subgraph of T induced by edges with label r. Each component of T' is a path since each fi is incident to at most two edges of T with label r. Let P be a component of T', and assume without loss of generality that P = fofi • • • fm-i. For each i, 0 < i < m — 2, starting at i = 0, choose ei i+1 in E(Ci) \ E with label r and ei+1i in G[Fi+1] satisfying condition (ii) of Lemma 2.7. This is possible because the Hamilton cycle □ has two edges labelled r in both rows two and four. Note that ei+1i G Ci+1 and has label r; this follows by the drawings of G[Fi] and G[Fi+1]. Add eiji+1 and ei+1ji to E.
(6)	For each — fj G A(T) with label c (Operations VI, VII and VIII), choose ei j in Ci with label c and ejii in G[Fj] that satisfies condition (ii) of Lemma 2.7. Note that eji G Cj and has label c; this follows by the drawings of G[Fi] and G[Fj]. Add ei,j and eji to E.
For each — fj G A(T) with label c (Operation IX), choose ei,j in E(Ci) \ E with label c/e and ej;i in G[Fj] satisfying condition (ii) of Lemma 2.7. This is possible because the Hamilton cycle c' has two edges labelled c/e in columns two and four, and fi is incident to at most one edge in T with label c and at most one edge in T with label e. Note that ejti g Cj and has label c/e; this follows by the drawings of G[Fi] and G[Fj]. Add ei,j and ej,i to E.
In the context of Operations IV and V, let T' be the subgraph of T induced by edges with label c. Each component of T' is a path since each fi is incident to at most two edges of T with label c. Let P be a component of T', and assume without loss of generality that P = f0f1 • • • fm-1. For each i, 0 < i < m — 2, starting at i = 0, choose ei i+1 in E(Ci) \ E with label c and ei+1i in G[Fi+1] satisfying condition
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
687
(ii) of Lemma 2.7. This is possible because the Hamilton cycles □ and c have two edges labelled c in both columns two and four. Note that ei+1i € Gi+1 and has label c; this follows by the drawings of G[Fj] and G[Fi+1]. Add ei i+1 and ei+1i to E.
(7) For each —/j € A(—) with label pm, choose eijj in E(Gj) \E and e^ in E(G[Fj]) \ E satisfying condition (ii) of Lemma 2.7. Add eijj and j to E.
Now eij and e^ have been chosen for all —/j € A(7?). By construction, (i) and (ii) of Lemma 2.7 are satisfied, and for each G[Fj], 0 < i < N - 1, the Hamilton cycle G» satisfies condition (iii) of Lemma 2.7. Therefore, G has a Hamilton cycle.	□
As a consequence of Lemmas 3.3, 3.5, 6.3 and 6.4, we now have our main result.
Theorem 1.1. If H is a 2-tree then k0(H) = 4, unless H = T V {u} for some tree T and vertex u, where T is a star on at least three vertices or the bipartition of V (T) has two even parts; in these cases, k0(H) = 5.
As pointed out in Section 1, if H is a k-tree then k + 2 < k0(H) < k + 3. For both 1-trees (i.e., trees) and 2-trees, equality can occur in both the upper and lower bound. By [6, Corollary 5.6] and Theorem 1.1, if H is a tree or 2-tree of diameter at least three, then the lower bound holds. We ask if this extends to k-trees, that is, if H is a k-tree with diameter at least three, is it the case that k0(H) = k + 2? On a related note, k-trees are a subclass of chordal graphs. We ask if the techniques presented here can be extended to determine the Gray code numbers of other chordal graphs.
References
[1]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
[2]	P. Bonsma and L. Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theoret. Comput. Sci. 410 (2009), 5215-5226, doi:10.1016/j. tcs.2009.08.023.
[3]	M. Celaya, K. Choo, G. MacGillivray and K. Seyffarth, Reconfiguring k-colourings of complete bipartite graphs, Kyungpook Math. J. 56 (2016), 647-655, doi:10.5666/kmj.2016.56.3. 647.
[4]	L. Cereceda, J. van den Heuvel and M. Johnson, Connectedness of the graph of vertex-colourings, Discrete Math. 308 (2008), 913-919, doi:10.1016/j.disc.2007.07.028.
[5]	C. C. Chen and N. F. Quimpo, On strongly hamiltonian abelian group graphs, in: K. L. McA-vaney (ed.), Combinatorial Mathematics VIII, Springer, Berlin, volume 884 of Lecture Notes in Mathematics, pp. 23-34, 1981, doi:10.1007/bfb0091805, proceedings of the Eighth Australian Conference held at Deakin University, Geelong, August 25 - 29, 1980.
[6]	K. Choo and G. MacGillivray, Gray code numbers for graphs, Ars Math. Contemp. 4 (2011), 125-139, doi:10.26493/1855-3974.196.0df.
[7]	T. Dvorak, Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math. 19 (2005), 135-144, doi:10.1137/s0895480103432805.
[8]	M. Dyer, A. Flaxman, A. Frieze and E. Vigoda, Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures Algorithms 29 (2006), 450-465, doi:10.1002/rsa.20129.
688
Ars Math. Contemp. 17 (2019) 493-514
[9] S. Fallat and L. Hogben, Minimum rank, maximum nullity, and zero forcing number of graphs, in: L. Hogben (ed.), Handbook of Linear Algebra, Chapman & Hall/CRC, New York, Second Edition, 2nd edition, 2013, doi:10.1201/b16113.
[10]	S. Finbow and G. MacGillivray, Hamiltonicity of Bell and Stirling colour graphs, preprint.
[11]	R. Haas, The canonical coloring graph of trees and cycles, Ars Math. Contemp. 5 (2012), 149157, doi:10.26493/1855-3974.168.464.
[12]	R. Haas and K. Seyffarth, The k-dominating graph, Graphs Combin. 30 (2014), 609-617, doi: 10.1007/s00373-013-1302-3.
[13]	R. Haas and K. Seyffarth, Reconfiguring dominating sets in some well-covered and other classes of graphs, Discrete Math. 340 (2017), 1802-1817, doi:10.1016/j.disc.2017.03.007.
[14]	T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara and Y. Uno, On the complexity of reconfiguration problems, Theoret. Comput. Sci. 412 (2011), 1054-1065, doi:10.1016/j.tcs.2010.12.005.
[15]	T. Ito, M. Kaminski and E. D. Demaine, Reconfiguration of list edge-colorings in a graph, Discrete Appl. Math. 160 (2012), 2199-2207, doi:10.1016/j.dam.2012.05.014.
[16]	M. Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures Algorithms 7 (1995), 157-165, doi:10.1002/rsa.3240070205.
[17]	G. J. Simmons, Almost all n-dimensional rectangular lattices are Hamilton-laceable, in: F. Hoffman, D. McCarthy, R. C. Mullin and R. G. Stanton (eds.), Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathe-matica Publishing, Winnipeg, Manitoba, volume XXI of Congressus Numerantium, pp. 649661, 1978, held at Florida Atlantic University, Boca Raton, Florida, January 30 - February 2, 1978.
[18]	A. Suzuki, A. E. Mouawad and N. Nishimura, Reconfigurations of dominating sets, in: Z. Cai, A. Zelikovsky and A. Bourgeois (eds.), Computing and Combinatorics, Springer, Cham, volume 8591 of Lecture notes in Computer Science, pp. 405-416, 2014, doi:10.1007/ 978-3-319-08783-2_35, proceedings of the 20th International Conference (COCOON 2014) held in Atlanta, GA, August 4 - 6, 2014.
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
689
Appendix A 3-colouring graphs of trees
A 2-tree with a dominating vertex u has the form T V {u} for some tree T. Lemma 3.5 characterizes when k0(T V {u}) = 5. Its proof requires a technical result (Lemma 3.6) that we prove in this appendix. To do so, we introduce additional terminology along with structural results on the 3-colouring graphs of trees.
Define Li to be an assignment of lists to the vertices of T V {u} with Li (u) := {i} and Li(w) := {1, 2,3,4} for w G V(T). Then GLi (T V{u}) = G3(T) and thus, G4(T V{u}) can be partitioned into four copies of G3 (T) with edges between pairs of copies. We prove that when T has even number of vertices then G3 (T) is bipartite. First, we prove a more general result for GL(H) where H is a connected graph.
Lemma A.1. Let H be a connected graph on n vertices and L an assignment of lists to the vertices of H such that L(v) C {1,2,3} for each v G V(H). If H is L-colourable and there is a vertex w G V (H) with IL(w)l < 3, then GL(H) C Qn. In particular, GL(H) is a bipartite graph.
Proof. The proof is by induction on n. Observe that the result is true for n =1 and n = 2.
First suppose that IL(w)l = 1 and without loss of generality, L(w) = {1}. In any list colouring of H, each vertex v G NH(w) cannot be coloured '1'. Thus, let L be an assignment of lists of allowable colours defined as
LV):=iL(v) \{1}, if v G Nh(w), L(v),	otherwise.
Denote the components of H - w by H1,H2,..., HN. Then by the inductive hypothesis, for each i, 1 < i < N,
GL (Hi) C Q|V(Hi)|. Since w must be coloured using the colour '1', we have
GL(H) = Gl(H - w) = GL (u^Hi)
N
= □ Gl (Hi),	by Remark 2.4
i=1
N
C □ Q|V(Hi)|,	by the inductive hypothesis
i=1
= Qn-1.
Next suppose that IL(w)l = 2 and without loss of generality, L(w) := {1,2}. For i = 1,2, define Li as Li(w) := {i} and Li(v) := L(v) for v = w with v G V(H). Also define Li as Li(w) := {i} and Li(v) := {1,2,3} for v = w with v G V(H). Observe that Gl1 (H) C Gti (H) and Gl2 (H) C G^ (H). Furthermore, Gti (H) = G^ (H), and hence, GL(H) C G^ (H) □ K2. By the preceding argument, G^ (H) C Qn-1, and therefore
GL (H) C Qn-1 □ K2 = Qn.	□
Lemma A.2. If T is a tree with an even number of vertices then G3(T) is bipartite.
690
Ars Math. Contemp. 17 (2019) 493-514
Proof. If T = K2, then G3(T) = C6. Let T be a tree on an even number of vertices with | V(T) | > 4 having bipartition (A, B). Fix u G A, v G B with u adjacent to v in T. Define
H := G3(T). For each 1 < i = j < 3 let
Vîj := {c G V(H) | c(u) = i and c(v) = j}.
Then {Vi2, Vi3, V23, V2i, V3i, V32} is a partition of V(H). Observe each H[Vj] is connected (this can be shown by induction on |V(T)|), and that [Vap, V7(5] = 0 if and only if a = y or £ = J. It follows that Hi = H[Vi2 U V13 U V23 U V21] is connected, and by Lemma A.1 is bipartite. Similarly, H2 = H[V23 U V2i U V3i U V32] and H3 = H[V3i U V32 U Vi2 U Vi3] are connected and bipartite. Denote the two-coloured vertices of H (that is, the colourings of T with two colours) by cj G Vj such that
, I i, if x G A, c,-o(x) := < 3K ' \j, if x G B.
Suppose the bipartition of each H[Vj ] is (Aj, Bjj ) where c^j G Bjj.
If |A| and |B| are even, then dH(cjj, c^/j/) is even. It follows that
(Ai2 u Ai3 u A23 U A2i, Bi2 u Bi3 U B23 U B2i) is a bipartition of Hi,
(A23 U A2i u A3i U A32, B23 U B2i u B3i U B32) is a bipartition of H2 , and
(A3i U A32 U Ai2 U Ai3, B3i U B32 U Bi2 U Bi3) is a bipartition of H3. Hence,
A := (J Aij and B := J Bij
i<i=j<3	i<i=j<3
are independent, and thus form a bipartition of H.
If |A| and |B| are both odd, dH(cjj, c^/j/) is even if and only if i = i' and j = j'. It follows that
(Ai2 u Bi3 u A23 U B2i, Bi2 u Ai3 U B23 U A2i) is a bipartition of Hi ,
(A23 U B2i u A3i U B32, B23 U A2i u B3i U A32)
is a bipartition of H2 , and
(A3i U B32 U Ai2 U Bi3, B3i U A32 U Bi2 U Ai3)
is a bipartition of H3. Hence,
A = {A i2 U Bi3 U A23 U B2i U A3i U B32}
and
B = {Bi2 U Ai3 u B23 U A2i u B3i u A32} are independent, and thus form a bipartition of H.	□
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
691
Definition A.3. A connected bipartite graph with bipartition (A, B) is Hamilton laceable if there is a Hamilton path between any u G A and v G B.
Remark A.4. The following are Hamilton laceable.
1.	P^ □ Pfc2 □ Pfc3 □ ••• □ Pfc„, for n > 2 and kj > 1, 1 < i < n [17].
2.	Q„, for n > 1 [5].
Definition A.5. A B-graph with vertex partition {F0, Fi,..., FN _i} is a bipartite graph G with bipartition (A, B) together with a partition {F0, F1,..., FN_1} of V(G) so that, for i = 0,1,..., N — 1, G [Fi] is Hamilton laceable.
Lemma A.6. Let G be a B-graph with vertex partition {F0, F1,..., FN_1} and bipartition (A, B). Suppose for each i = 1,2,..., N — 1, there is an edge bi_1ai with 6i_1 G B n Fi_1 and G An Fi. Then G has a Hamilton path between any vertex in An F0 and any vertex in B n FN _1.
Proof. Let a0 G An F0 and bN_1 G B n FN_1. For each Fj, i = 0,1,..., N — 1, choose a Hamilton path P; in G[Fj] between bj and aj. Then
Corollary A.7. Let G be a B-graph with vertex partition {F0, F1,..., FN_1} and bipartition (A, B) such that [Fi_1, Fj] is a set of independent edges and |[Fi_1, Fj] | > 2, i = 1,2,..., N — 1. If for each i = 1,2,..., N — 1, the endpoints of any pair of edges in [Fj_1, Fj] induces a 4-cycle in G, then G has a Hamilton path between any vertex in An F0 and any vertex in B n FN _1.
Proof. Let a0 G An F0 and bN _1 G B n FN _1. For each [Fj_1, F, ], i = 1, 2,..., N — 1, choose two edges b^aj and bj^aj. Then G[{a^ aj, bj_ 1, bj_ 1}] induces a 4-cycle aiaibi_1bi_1ai. Note that either bj_1 G B or bj_1 G B. Without loss of generality, suppose bj_1 G B. Then aj G A. The result follows by Lemma A.6.	□
Definition A.8. An odd flare is a tree obtained from K1ji, t > 3 and odd, by a single subdivision of one edge.
Lemma 3.6. Let T be a tree with bipartition (A, B), where |A| := £ and |B| := r, and let G3(T) be the 3-colouring graph of T with colours C = {1, 2, 3}. Define cj to be the vertex of G3(T) with Cj (a) = i for all a G A and Cj (b) = j for all b G B.
(1)	If £, r > 0 are both even, then G3(T) has no spanning subgraph consisting only of paths whose ends are in {c12, c13, c21, c23, c31, c32}.
(2)	If £ > 1 is odd and r > 0 is even, then G3(T ) has a Hamilton path from c12 to c23.
(3)	If £ > 1 and r > 1 are both odd, then G3(T ) has a Hamilton path from c12 to c13.
are the edges of a Hamilton path in G between a0 and _i.
□
692
Ars Math. Contemp. 17 (2019) 493-514
Proof. (1): Suppose £,r > 0 are both even. By Lemma A.2, H := G3(T) is bipartite. Suppose H has bipartition (A, B). Without loss of generality, assume c12 g A. Since dH(c12, cij) is even for each cij G {c12, c13, c21, c23, c31,c32} and H is bipartite, we have {ci2,c13, c21,c23, c31, c32} C A. By [6, Theorem 5.5] there is a Hamilton cycle in H, and thus |A| = |B|. It follows that there is no spanning subgraph of H consisting only of paths whose ends are in {c12,c13, c21,c23, c31,c32} (otherwise |A| > |B|).
(2): Suppose l> 1 is odd and r > 0 is even. Then I + r > 5. We first prove that G3 (T) has a Hamilton path between c12 and c23 whenever T is P5 or any odd flare. If T = P5 (with |A| = 3, |B| = 2), then there is a Hamilton path between c12 to c23 in G3(P5), as described in Figure 15. A 3-colouring f of P5 = x1x2x3x4x5 is represented by the string f (x1)f (x2)f (x3)f (x4)f (x5); for example, c12 = 12121 and c23 = 23232.
12121	21313	32321	13131	23231	31212
12321	21323	32121	12131	13231	31232
12323	21321	32123	32131	13232	31231
12313	31321	12123	32132	13212	21231
12312	31323	13123	12132	13213	21232
32312	31313	23123	13132	23213	21212
31312	32313	23121	23132	21213	23212
21312	32323	13121	23131	31213	23232
Figure 15: A Hamilton path in G3(P5) from c12 to c23.
Let T be an odd flare on n vertices with u denoting the unique vertex of degree two and let Nt(u) = {v, v'} where v is the unique vertex of degree n - 2 (Figure 16).
v	u
(n - 3)
Figure 16: An odd flare T.
Here |A| = n - 2 and |B| = 2. We partition H := G3(T) according to the colours of
u and v. For each 1 < i = j < 3, let Vij := {c G V(H) | c(u) = i and c(v) = j} and let Lij be an assignment of lists to the vertices of H such that Lij (u) := {i}, Lij (v) := {j} and Lij(w) := {1,2, 3} for w G V(H - {u, v}). Note that GLjj (H) = H[Vij] = Qn-2, for each 1 < i = j < 3. Let H1 := HV2 U V12] = Qn-3 □ PI, H4 := H[V21 U V31] = Qn-3 □ P4, H2 := H[V13], and H3 := HW23].
For {i,j,k} = {1,2,3}, let dijk G V(H) denote the vertex with dijk(v) = j, dijk(v') = k, and djk(w) = i for all w G Nt(v). Then [VU,V13] = {c^d^, du3c^} and [V23, V21] = {c21d231, d213c23}.
Claim. For m > 2, every edge of Qm □ P4 is in a Hamilton cycle of Qm □ P4.
The claim follows by induction and the fact that any pair of distinct edges of Qm-1 (m > 3) belongs to a Hamilton cycle of Qm-1 (for example, see [7, Theorem 4.1]).
In what follows, we define cycles and paths to construct a Hamilton path from c12 to c23 in G3(T) when T is an odd flare on n vertices. See Figure 17 for the case n = 5; here,
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
693
the labels of the two columns of Vjj represent the colour choices for v' and the labels of the rows of Vjj represent the colour choices for the two vertices in (v) \ {u}. Let C be a Hamilton cycle of H containing c12d123 and C4 be a Hamilton cycle of H4 containing d213c21; these exist by the previous claim. Let c G NH3 (c23) have c(v') = 3 and d G V13 be the unique vertex of H2 adjacent to c. By [7, Theorem 4.1], there is a Hamilton cycle C3 in H3 containing the edges cc23 and c23d231. Observe dH2 (d, c13) is odd. Since H2 is Hamilton laceable, there is a Hamilton path P between d and c13 (see Figure 17).
Figure 17: H = G3(T), T an odd flare on five vertices, along with C1, P, C3, and C4. Now,
(C1 - {C12d123}) u {d123C13} U P U {dc} U (C3 - {C23C, C23d231})
u {d231C21} u (C4 - {C21d213}) u {d213C23} is a Hamilton path in H between c12 and c23 (see Figure 18 for n = 5).
Figure 18: A Hamilton path between c12 and c23 in H = G3(T), T an odd flare on five vertices.
Now suppose T is a tree on n > 5 vertices with n odd that is not isomorphic to a star or an odd flare. Then there are leaves x, y G V(T) with dT(x, y) > 3. By choosing leaves x and y so that dT(x, y) > 3 is minimum, T' := T - {x, y} is not a star. Let (x) := {x'} and (y) := {y'}; since dT(x, y) > 3, x' = y'.
Let (a', B') denote the bipartition of T' with A' C A, B' C B, and define cjj- to be the vertex of H' := G3(T') with cjj.(a) = i for all a G A' and cjj. (b) = j for all b G B'. By the inductive hypothesis, H' has a Hamilton path between c'12 and c23. Let V (H') := {/0, /1;..., /N_1}. Since H' has a Hamilton path, we may assume that /o/1 • • • /N-1 is a Hamilton path in H' between /0 = c'12 and /N_1 = c23. Since c'12 and c23 differ in colour on at least two vertices, /0 is not adjacent to /N_1 in H'.
694
Ars Math. Contemp. 17 (2019) 493-514
For 0 < i < N — 1, let Fj be the set of 3-colourings of H that agree with / on V(T'). Then {Fo, Fi,..., Fn-1} is a partition of the vertices of H, and H[Fj] = C4, 0 < i < N — 1. If /j-1 and / differ on the colour of a vertex of V(T') \ {x', y'}, then |[Fj-1, Fj]| = 4 and H[Fj-1 U Fj] = Q3. Otherwise, /j-1 and / differ on the colour of x' or y', implying that | [Fj-1, Fj] | = 2, the subgraph of H induced by the endpoints of the edges of [Fj-1, Fj] is a 4-cycle, and H[F-1 U Fj] = P4 □ K.
Consider the spanning subgraph G of H with edge set
/N-1	\ /N-1	\
Ue (H[Fj]) U [Fj-1, Fj]
Note that G is a connected B-graph. Let (A, B) be the bipartition of G and assume
C12 € A.
First suppose c23 € B. As c12 € F0 and c23 € FN-1, it follows from Corollary A.7 that there is a Hamilton path in G between c12 and c23. Now suppose c23 € A. Since (c12, c23) is odd, H must have an edge e with both endpoints in A or both endpoints in B. Suppose e € [Fp, Fq ], where 0 < p < q < N — 1. Since /0 is not adjacent to /N -1 in H', either p = 0 or q = N — 1. Without loss of generality we assume p = 0. Then /p/q € E(H'), and either
(i)	| [Fp, Fq] | =4 and H[Fp U Fq] = Q3, or
(ii)	| [Fp, Fq] | = 2, the subgraph of H induced by the endpoints of the edges of [Fp, Fq] is a 4-cycle, and H[Fp U Fq] = P4 □ K2.
In either case, there exists another edge e' € [Fp, Fq] such that e := uv, e' := u'v', u, u' € Fp, and uvv'u'u is a 4-cycle. The choice of e = uv ensures that u, v € A or u, v € B.
Consider the spanning tree T of H' with edge set E(T) := {/j-1/j | 1 < i < q — 1} U {/j-1/j | q + 1 < i < N — 1} U {/p/q}. We define J to be the spanning subgraph of H with edge set
m E(H[Fj])J U I U [Fj, Fj] Vj=0	/ V/i/j eE(TT)
Then J is a connected B-graph. Let (K, L) be the bipartition of J; we may assume that c12 € K. Since /p/q € E(T), [Fp, Fq] C E( J); in particular, e = uv and e' = u'v' are edges of J, so u and v are in different parts of the partition (K, L), and thus c23 € L.
Case 1. If |[Fp, Fp+1]| = |[Fp, Fq]| = 2, then /p/q, /p/p+1 € E(H') arise from colour changes on x' and y'. Since there are only three possible vertex colours, there is only one possible colour that x' could change to, and only one possible colour that y' could change to; i.e., one of /p/q, /p/p+1 arises from a colour change on x' and the other from a colour change on y'. Assuming that H[Fp] is the 4-cycle uu'ww'u, it follows that u, u' are incident to the edges of [Fp, Fq] and that without loss of generality u', w are incident to the edges of [Fp, Fp+1].
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
695
Let [Fp,Fq] = {uv,u'v'} and [Fp, Fp+1] = {wz,u'z'}. Since uu' G E(J), exactly one of u, u' is in L.
Case 1(a). First suppose that u g L. Let J1 denote the subgraph of J induced by up=0Fj. Then J1 is a B-graph with vertex partition {F0, F1;..., Fp} and bipartition (K, L) satisfying the conditions of Corollary A.7, with c12 G K n F0 and u G L n Fp. Thus J1 has a Hamilton path R1 between c12 and u. Note that the proof of Corollary A.7 implies that R1 can be constructed so as to contain the edge u'w.
Let J2 be the subgraph of J induced by UN_ 1Fj. Then J2 is a B-graph with vertex partition {Fq, Fq+1,..., FN_1} and bipartition (K, L) satisfying the conditions of Corollary A.7, with v G K n Fq and c23 G L n FN_1. Thus J2 has a Hamilton path R2 between v and c23.
Finally, let J3 be the subgraph of J induced by U^—pF,. Then by Lemma 2.7, J3 has a Hamilton cycle C containing the edges uu', ww' and uw'. Let R3 be the path between u' and w obtained by deleting u and w' from C.
Now concatenate paths R1, R2, R3 and delete edge u'w G R1 to form a Hamilton path between c12 and c23.
Case 1(b). Now suppose that u G K. Then u' G L. Since p > 1 and |[Fp,Fp+1]| = |[Fp,Fq ]| = 2, we have |[Fp-1,Fp]| = 4. Let t G Fp-1 be such that tu G [Fp-1,Fp]. Then t G L.
Let J1 denote the subgraph of J induced by Up=_01Fj. Then J1 is a B-graph with vertex partition {F0, F1,..., Fp-1} and bipartition (K, L) satisfying the conditions of Corollary A.7, with c12 G K n F0 and t G L n Fp-1. Thus J1 has a Hamilton path R0 between c12 and t. Let R1 be the concatenation of paths R0 and tuw'wu'.
We define J2 and R3 as in Case 1(a). The same argument with v' in place of v gives a Hamilton path R2 between v' and c23. Now concatenate paths R1, R2, R3 and delete edge u'w G R1 to form a Hamilton path between c12 and c23.
Case 2. Suppose |[Fp, Fq]| = 4 and label the 4-cycle of H[Fp] as uu'ww'u. Let J3 be the subgraph of J induced by U^—pF, . Then by Lemma 2.7, J3 has a Hamilton cycle C. Without loss of generality, suppose C contains the edges uu', ww' and uw'. Let R3 be the path between u' and w obtained by deleting u and w' from C.
Let J1 denote the subgraph of J induced by Up=0F,. Then J1 is a B-graph with vertex partition {F0, F\,..., Fp} and bipartition (K, L) satisfying the conditions of Corollary A.7, with c12 G K n F0. Thus J1 has Hamilton paths R1 and R'/ between c12 and the two vertices in L n Fp. Let R1 be one of R1 and R1' such that R1 contains edge u'w. Suppose R1 is between c12 and t. Then t g L. Let t' g Fq be such that tt' g [Fp, Fq]. Then t' G K.
We define J2 as in Case 1(a). The same argument with t' in place of v gives a Hamilton path R2 between t' and c23. Now concatenate paths R1, R2, R3 and delete edge u'w g R1 to form a Hamilton path between c12 and c23.
Case 3. Suppose | [Fp, Fp+1] | = 4. Let J1 denote the subgraph of J induced by (Up=0Fj) U (U^-1 F,). Then J1 is a B-graph with vertex partition
{F0, F1, . . . , Fp, Fq, Fq+1, . . . , Fn-1}
and bipartition (K, L) satisfying the conditions of Corollary A.7, with c12 G K n F0 and c23 G L n Fn_ 1. Thus J1 has a Hamilton path R between c12 and c23. Note that the proof
696
Ars Math. Contemp. 17 (2019) 493-514
of Corollary A.7 implies that R can be constructed so as to contain three edges of H[Fp].
Let J3 be the subgraph of J induced by uq-p+Fj. Then by Lemma 2.7, J3 has a Hamilton cycle C. Note that C contains three edges of H[Fp+1].
By the Pigeonhole Principle there are s, t G Fp and s', t' G Fp+1 with st G R, s't' G C such that ss'tt's is a 4-cycle in H[Fp U Fp+1 ]. Now (R U C) - {st, s't'} is a Hamilton path in J between c12 and c23.
(3): Finally suppose, I > 1 and r > 1 are both odd. We define £sfct to be the tree obtained from Pk with ends u and v by appending s leaves to u and t leaves to v. The proof is by induction and has the following base cases.
Base Case 1. We first prove that H := G3(T) has a Hamilton path between c12 and c13 when T = £4,0+2 for k > 0, that is, when T = P4fc+2. If T = P2 then c12c32c31c21c23c13 is such a Hamilton path. Suppose k > 0 and T = P4k+2. Let u and v be the leaves of T, NT(u) := {u'}, NT(v) := {v'}, NT(u') := {u,u''} and NT(v') := {v,v''}. Then T' := T - {u, u', v, v'} is isomorphic to P4(fc_1)+2. Let (A', B') denote the bipartition of T' with A' Ç A, B' Ç B, and define cj^ to be the vertex of H' := G3(T') with cj(a) = i for all a G A' and cj (b) = j for all b G B'. By the inductive hypothesis, H' has a Hamilton path between c'12 and c'13. Let V(H') := {/0, f1,..., /Nt1}. Since H' has a Hamilton path we may assume that /0/1 • • • /Nt1 is a Hamilton path in H' between /0 := c'12 and
_1 := c13.
For 0 < i < N - 1, let Fj be the set of 3-colourings of H that agree with / on V(T'). Then {Fo, F1,..., Fn-1} is apartition of the vertices of H, and H[Fj] = P4 □ P4, 0 < i < N - 1. If /jt1 and /j differ on the colour of a vertex of V(T') \ {u'', v''}, then | [Fj_1, Fj] | = 16 and H[Fjt1 U Fj] = (P4 □ P4) □ K2. Otherwise, /jt1 and /j differ on the colour of u'' or v'', implying that | [Fj—1, Fj] | = 8, and the subgraph of H induced by the endpoints of the edges of [Fj—1, Fj] is C4 □ P4.
Consider the spanning subgraph G of H with edge set
(N _1	\ / N _1
U E(H[Fj]H u( y [Fj_1, Fj]
i=0 J \j=1
Note that by Remark A.4, G is a connected B-graph. Let (A, B) be the bipartition of G and assume c12 G A. Since H is bipartite by Lemma A.2, and dH(c12, c13) is odd, c13 G B. As c12 G F0 and c13 G FN_1, it follows from Corollary A.7 that there is a Hamilton path in G between c12 and c13.
Base Case 2. Let T = £24sfc2 2 or T = f4sfc+1j2i+1 with s, t > 1, k > 0, and T' = P4fc+2 be obtained from T by deleting 2s leaves adjacent to u and 2t leaves adjacent to v.
Let (A', B') denote the bipartition of T' with A' Ç A, B' Ç B, and define cj^ to be the vertex of H' := G3(T') with cj^(a) = i for all a G A' and cj^ (b) = j for all b G B'. By Case 1, H' has a Hamilton path between c'12 and c'13. Let V(H') := {/0, /1,..., /N_1}. Since H' has a Hamilton path we may assume that /0/1 • • • /N_1 is a Hamilton path in H' between /0 := c'12 and /N_1 := c'13.
For 0 < i < N -1, let Fj be the set of 3-colourings of H := G3(T) that agree with /j on V (T'). Then {F0, F1,..., Fn _1} is apartition of the vertices of H, and H[Fj] = Q2s+2î, 0 < i < N - 1. If /j_1 and /j differ on the colour of a vertex of V(T') \ {u, v}, then |[Fj_1, Fj] | = 22s+2t and H[Fj_1 U Fj] = Q2s+2î □ K2 = Q2,+2t+1. If /j_1 and /j differ on the colour of u then |[Fj_1, Fj]| = 22t, and the subgraph of H induced by the
M. Cavers and K. Seyffarth: Reconfiguring vertex colourings of 2-trees
697
endpoints of the edges of [Fi-i, Fi] is Q2i+i. Otherwise /j_i and / differ on the colour of v implying that | [Fj_1, Fj] | = 22s, and the subgraph of H induced by the endpoints of the edges of [Fj_i, Fj] is Q2s+i.
Consider the spanning subgraph G of H with edge set
Note that by Remark A.4, G is a connected B-graph. Let (A, B) be the bipartition of G and assume ci2 G A. Since H is bipartite by Lemma A.2, and dH(ci2, ci3) is odd, ci3 G B. As ci2 G F0 and ci3 G FN_i, it follows from Corollary A.7 that there is a Hamilton path in G between ci2 and ci3.
Base Case 3. Let T = f2sfc+iji with s, k > 1, and let T' ^ P4k_2 be obtained from T by deleting the 2s + 2 leaves and the vertices u and v. Define u', v' as the leaves of T' so that in T, u' is adjacent to u and v' is adjacent to v.
Let (A', B') denote the bipartition of T' with A' C A, B' C B, and define cj to be the vertex of H' := G3(T') with cj^(a) = i for all a G A' and cj (b) = j for all b G B'. By Case 1, H' has a Hamilton path between c'i2 and c'i3. Let V(H') := {/0, /i;..., /N_i}. Since H' has a Hamilton path we may assume that /0/i • • • /N_i is a Hamilton path in H' between /0 := c'i2 and /N_i := c'i3.
For 0 < i < N - 1, let Fj be the set of 3-colourings of H := G3(T) that agree with /i on V(T'). Then {Fo, Fi,..., Fw_i} is a partition of the vertices of H, and H[Fj] D P4 □ P22s+2, 0 < i < N - 1. This follows since GL(Kij2s+i) has a Hamilton path P22s+2 where L is an assignment of lists in which vertices of degree one have lists {1, 2, 3} and the remaining vertex has list {1, 2}. If /j_i and /j differ on the colour of a vertex of V(T') \ {u', v'}, then |[Fi_i,Fj]| = 4• 22s+i andH[Fj_iUFj] D (P4 □ P22=+i) □ K2. If /j_i and /j differ on the colour of v' then | [Fj_i, Fj] | =2 • 22s+i, and the subgraph of H induced by the endpoints of the edges of [Fj_i, Fj] contains (P2 □ P22s+i) □ K2. Otherwise /j_i and /j differ on the colour of u' implying that | [Fj_i, Fj] | =4 • 22s, and the subgraph of H induced by the endpoints of the edges of [Fj_i, Fj] contains (P4 □ P22s) □ K2.
Consider the spanning subgraph G of H with edge set
Note that by Remark A.4, G is a connected B-graph . Let (A, B) be the bipartition of G and assume ci2 G A. Since H is bipartite by Lemma A.2, and (ci2, ci3) is odd, ci3 G B. As ci2 G F0 and ci3 G FN_i, it follows from Corollary A.7 that there is a Hamilton path in G between ci2 and ci3.
Induction Step. Now suppose T is a tree with bipartition (A, B), where |A| := I > 1 and |B| := r > 1 are both odd and T is not isomorphic to any of the graphs in Base Cases 1 to 3. If every pair of leaves x, y G A or x, y G B satisfy (x, y) < 2, then T = fsfct; since r > 1 are both odd, T is isomorphic to one of the graphs in Base Cases 1 to 3. Thus, there are leaves x, y G A (or x, y G B) with (x, y) > 3.
Case 1. If T - {x,y} is a star, then T is the graph obtained from Kij2s+i, s > 1, by subdividing two of its edges. Let u g V(T) be the vertex of degree 2s + 1 and v G V(T) a leaf adjacent to u. Define T' := T[{u, v}] and observe T' = K2.
698
Ars Math. Contemp. 17 (2019) 493-514
Let W' := G3(T') have Hamilton path /0/1/2/3/4/5 := c'12c'32c'31c'21c'23c'13, where cij(u) = i and cjj(v) = j. For 0 < i < 5, let Fj be the set of 3-colourings of W := G3(T) that agree with / on V(T'). Then {F0, F1;..., F5} is a partition of the vertices of W, and W[Fj] = P4 □ P4 □ Q2s_2, 0 < i < 5. If /i-1 and / differ on the colour of vertex v, then |[Fj_1, Fj]| = 4 • 4 • 22s_2 and W[Fj_1 U Fj] = (P4 □ P4 □ Q2s_2) □ K2. If /j_1 and / differ on the colour of u then | [Fj_1, Fj] | = 4, and the subgraph of W induced by the endpoints of the edges of [Fj_1, Fj] is C4.
Consider the spanning subgraph G of W with edge set
Note that by Remark A.4, the graph P4 □ P4 □ Q2s_2 is Hamilton laceable since P4 □ P4 □ P22s-2 is a Hamilton laceable spanning subgraph. Thus, G is a connected B-graph. Let (A, B) be the bipartition of G and assume c12 6 A. Since W is bipartite by Lemma A.2, and dH(c12, c13) is odd, c13 6 B. As c12 6 F0 and c13 6 F5, it follows from Corollary A.7 that there is a Hamilton path in G between c12 and c13.
Case 2. Suppose NT(x) := {x'} and NT(y) := {y'}, and that T' := T - {x, y} is not a star. Let (A', B') denote the bipartition of T' with A' C A, B' C B, and define cj^ to be the vertex of W' := G3(T') with cj^ (a) = i for all a 6 A' and cj^(b) = j for all b 6 B'.
By the inductive hypothesis, W' has a Hamilton path between c'12 and c'13. Let V(W') := {/0, /1;..., /N_1}. Since W' has a Hamilton path we may assume that /0/1 • • • /N_1 is a Hamilton path in W' between /0 := c'12 and /N_1 := c'13.
For 0 < i < N — 1, let Fj be the set of 3-colourings of W := G3 (T) that agree with /j on V(T'). Then {F0, F1;..., FN_1} is a partition of the vertices of W, and W[Fj] = C4, 0 < i < N — 1. If /j_1 and /j differ on the colour of a vertex of V(T') \ {x', y'}, then |[Fj_1, Fj]| =4 and W[Fj_1 U Fj] = Q3. Otherwise, /j_1 and /j differ on the colour of x' or y', implying that | [Fj_1, Fj] | = 2, the subgraph of W induced by the endpoints of the edges of [Fj_1, Fj] is a 4-cycle, and W[Fj_1 U Fj] = P4 □ K.
Consider the spanning subgraph G of W with edge set
Note that G is a connected B-graph. Let (A, B) be the bipartition of G and assume ci2 g A. Since H is bipartite by Lemma A.2 and dH(c12, c13) is odd, c13 g B. As c12 g F0 and c13 g Fn_1, it follows from Corollary A.7 that there is a Hamilton path in G between c12
and c13.
□