Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 149–157
The canonical coloring graph of trees and cycles∗
Ruth Haas †
Smith College, Northampton, MA 01063, USA
Received 1 August 2010, accepted 13 October 2011, published online 20 January 2012
Abstract
For a graph G and an ordering of the vertices π, the set of canonical k-colorings of G
under π is the set of non-isomorphic proper k-colorings ofG that are lexicographically least
under π. The canonical coloring graph Canπk (G) is the graph with vertex set the canonical
colorings of G and two vertices are adjacent if the colorings differ in exactly one place.
This is a natural variation of the color graph Ck(G) where all colorings are considered. We
show that every graph has a canonical coloring graph which is disconnected; that trees have
canonical coloring graphs that are Hamiltonian; and cycles have canonical coloring graphs
that are connected.
Keywords: Graph coloring, Canonical coloring
Math. Subj. Class.: 05C15
1 Introduction
For a positive integer k and a graph G, the k-coloring graph of G, Ck(G), is the graph
whose vertex set is the set of proper k vertex colorings of G. Two k colorings are joined by
an edge if they differ in color on just one vertex ofG. The basic question of whether Ck(G)
is connected has recieved significant attention, see for example [1, 5, 6, 8]. In theoretical
physics Ck(G) appears in the Glauber dynamics of an anti-ferromagnetic Potts model at
zero temperature. In Glauber dynamics, the state space of the Markov chain is the set of all
k-colorings of a graph. Markov processes also give a method to approximate the number of
k-colorings of G. If Ck(G) is connected, the probabilities of moving between colorings in
Ck(G) can be assigned so that the stationary distribution is uniform on all proper colorings.
If the process converges fast enough (in polynomial time) then repeated sampling can be
used to obtain a reasonable approximation of the total number of proper colorings. There is
an extensive literature on when there is rapid mixing of Ck(G) see for example [5, 6, 7, 8].
∗In memory of Michael Albertson, who provided primary colors in my graph theory toolbox.
†This research was partially supported by NSF grant DMS–0721661.
E-mail address: rhaas@smith.edu (Ruth Haas)
Copyright c© 2012 DMFA Slovenije
150 Ars Math. Contemp. 5 (2012) 149–157
1212, 2121, 1313
3131, 2323, 3232
1232, 2131, 1323
3121, 2313, 3212
1213, 2123, 1312
3132, 2321, 3231
1231, 2132, 1321
3123, 2312, 3213






Q
Q
Q
Q
Q
Q 





Q
Q
Q
Q
Q
Q
Figure 1: I3(P4)
Recently, several groups of graph theorists have given conditions which ensure the
connectivity of Ck for classes of graphs. Moreover, they have shown that there is no such
condition that depends only on the chromatic number χ(G).
Proposition 1.1 (Cereceda, van den Heuvel, and Johnson [1]). There is no function F (χ),
so that for all graphs G and integers k > F (χ(G)), Ck(G) is connected.
Recall the coloring number, col(G), is the smallest integer t for which there exists an
ordering of the vertices v1, . . . vn, such that for all i the degree of vi in the induced graph
on v1, . . . vi is less than t. That is, there exists an ordering of the vertices so that G can be
greedily colored using t colors.
Theorem 1.2 (Dyer, Flaxman, Frieze, Vigoda [3]). For any graph G and integer k ≥
col(G) + 1, Ck(G) is connected.
Beyond whether Ck(G) is connected, MacGillivray and Choo have shown that for all
graphs G, Ck(G) is Hamiltonian for sufficiently large k.
Theorem 1.3 (Choo and MacGillivray [2]). If k ≥ col(G)+2, then Ck(G) is Hamiltonian.
In this paper we consider only non-isomorphic colorings of a graph G and give some
conditions for when the graph of such colorings is connected and Hamiltonian. Section 2
provides definitions and basic results. Sections 3 and 4 give results for trees and cycles
respectively.
2 The canonical coloring graph
Two colorings of G are isomorphic if one results from permuting the names of the col-
ors only (i.e, we do not consider automorphisms of the graph). They are non-isomorphic
otherwise. It is natural to consider the variation of the coloring graph where the vertices
correspond to isomorphism classes of colorings of G. For simplicity, we will refer to each
vertex as a coloring of G (rather than an isomorphism class of colorings). There are several
ways to define the edge set. This paper will mainly look at the canonical coloring graph
defined below. Another possibility is the isomorphic coloring graph, Ik(G), which is de-
fined to be the graph with an edge between two colorings c, d if some representative of c
R. Haas: The canonical coloring graph of trees and cycles 151
differs at exactly one vertex from some representative of d. Figure 1 shows I3(P4), where
P4 is the path on 4 vertices.
Proposition 2.1. If Ck(G) is connected then so is Ik(G).
Proof. There is natural graph homomorphism from Ck(G) to a multigraph which is Ik(G)
with the addition of loops at each vertex.
On the other hand, Ik(G) may be connected when Ck(G) is not. For example, I3(C5)
is also C5 while C3(C5) is two disjoint 15 cycles.
For a graph G and an ordering of the vertices π, the set of canonical k-colorings of
G under π is the set of non-isomorphic proper k-colorings of G that are lexicographically
least under π. The canonical coloring graph Canπk (G) is the graph whose vertices are the
canonical colorings of G where two vertices are adjacent if the colorings differ in exactly
one place. The order π of vertices of G can result in different Canπk (G). For example,
Figure 2 shows Canπi3 (P4) for three different orderings of the vertices. In each case the
path is formed by edges {(1, 2), (2, 3), (3, 4)}. If the vertices are colored in the same order
as the path, π1 = (1, 2, 3, 4), the canonical coloring graph Canπ13 (P4) is a path (Figure
2a). For π2 = (1, 3, 2, 4), canonical coloring graph Canπ23 (P4) is a pair of disjoint edges
(Figure 2b). For π3 = (3, 2, 1, 4), canonical coloring graph Canπ23 (P4) is a cycle (Figure
2c). Thus properties of Canπk (G) may depend on the order π. Indeed, whenever G is not a
complete graph there exists an order for which Canπk (G) is disconnected.
Theorem 2.2. Let G 6= Kn be a connected graph and k ≥ χ(G) + 1. Then there exists an
order π such that Canπk (G) is disconnected.
Proof. Observe that if G is connected on n > 2 vertices and not complete then it contains
an induced P3. Let π be an ordering of the vertices (a, b, c, . . . ) such that (a, c), (b, c) ∈
E(G) and (a, b) 6∈ E(G). Now every canonical coloring of G must begin either 112 . . . or
123 . . . . Every coloring of the first kind differs in (at least) two places from every coloring
of the second kind, thus as long as there is at least one coloring of each kind, the graph
Canπk (G) is disconnected. Since there is a canonical proper coloring with χ(G) colors,
at least one of coloring will be obtained with χ(G) colors. A proper coloring of the first
kind is obtained by taking a proper coloring of G with exactly χ(G) colors, changing the
color on vertices a and b to the (χ + 1) color and recoloring to get the canonical coloring
isomorphic to this. A proper coloring of the second kind is obtained by taking a proper
coloring of G with exactly χ(G) colors, changing only the color on vertex b to the (χ+ 1)
color and recoloring for the canonical coloring isomorphic to this.
3 Trees
In this section we give conditions so that the canonical coloring graph of a tree has a
Hamilton cycle.
Theorem 3.1. For T a tree with n ≥ 4 vertices, and k ≥ 3 colors, there is an order π of
the vertices such that Canπk (T ) has a Hamilton cycle.
Proof. The proof is in three parts. We first show the result for stars, then for trees using at
least 4 colors, and finally for trees using exactly three colors.
152 Ars Math. Contemp. 5 (2012) 149–157
r r r r
1 2 3 4
r r r r
1 3 2 4
r r r r
3 2 1 4
1212 1231
1213
1232


HHH

1122 1231
1123
1233



1212 1233
1213
1232


HHH
H
HH

(a) (b) (c)
Figure 2: P4 and Canπ3 (P4) for three different orderings of the vertices of P4. The colors
are listed in the order given by the permutation.
Part I: Stars. Let Sn be the star with n ≥ 4 vertices and k ≥ 3 colors, let π be an
ordering of the vertices such that the root is first.
We first address the case where k = 3. It is straightforward to check if n ≤ 3
Canπ3 (Sn) has a Hamilton path (though not a cycle). Assume now there is a Hamilton
path on Canπ3 (Sn−1), specifically colorings c1, c2, . . . , cN . Every coloring of Sn is ob-
tained by taking a coloring ci of Sn−1 and choosing either color 2 or 3 for the nth vertex.
Now Canπ3 (Sn) = Can
π
3 (Sn−1)
⊗
K2, the Cartesian product. Hence Canπ3 (Sn) has a
Hamilton cycle if Canπ3 (Sn−1) has a Hamilton path.
For k > 3, if n = 1, 2, 3, Canπk (Sn) = Can
π
3 (Sn) has a Hamilton path. A Hamilton
cycle on Canπk (S4) is given by 1223, 1222, 1232, 1234, 1233.
Assume there is a Hamilton cycle on Canπk (Sn−1), specifically colorings c1, c2, . . . , cN.
Choose cN , c1 so that they both use at least colors 1, 2, 3. Every coloring of Sn is obtained
by taking a coloring ci of Sn−1 and choosing a color from 2, 3, . . . , ri ≤ k for the nth
vertex, where ri = min{k, 1+ largest color used in ci}. Let cji denote the coloring of Sn
that agrees with coloring ci on the first n− 1 vertices and is color j on the nth vertex. The
following is a Hamilton cycle on all the colorings of Canπk (Sn):
c41, c
5
1, . . . , c
r1
1 , c
3
1, c
2
1,
c22, c
4
2, c
5
2, . . . , c
r2
2 , c
3
2,
c33, c
4
3, c
5
3, . . . c
r3
3 , c
2
3,
c24, c
4
4, c
5
4, . . . , c
r4
4 , c
3
4,
. . .
< c2N , c
3
N >, c
5
N , . . . , c
rN
N , c
4
N
where the order of < c2N , c
3
N > depends on the parity of N .
Part II: Trees with k > 3 colors. Order the vertices v1, . . . vn so each vertex vi is a leaf
of the tree induced by v1, . . . vi. For n = 4, the case where T is a star was considered above.
The other tree on 4 vertices is a path. A possible ordering of the vertices and the resulting
Hamilton cycle for Canπk (P4) is shown in Figure 2(c). Again we proceed by induction
R. Haas: The canonical coloring graph of trees and cycles 153
on n. Let T ′ = T − vn. By assumption Canπk (T ′) has a Hamilton cycle c1, c2, . . . , cN .
We may take c1 to be the unique coloring that uses only two colors. For any i, ci can be
extended to a coloring of T by coloring vn. Let Fi be the set of colors for vn compatible
with ci and let ĉi be the set of colorings of T that agree with ci on T ′. All colorings of T
are obtained this way. Vertex vn can receive any color already used except the one used on
its unique neighbor vq . If only r < k colors have been used in ci then color r + 1 can be
used as well. Thus |F1| = 2 and |Fi| ≥ 3 for i > 1.
As in the part I of the proof we will proceed by using all colorings of ĉ1 followed by
those of ĉ2 etc., returning to ĉ1. Note that for all i the induced graph on ĉi is complete.
Thus we merely need to ensure there is an edge between ĉi−1 and ĉi that uses a different
vertex in ĉi than some edge between ĉi and ĉi+1.
If ci and ci+1 use the same color for vertex vq then |Fi ∩ Fi+1| = min(|Fi|, |Fi+1|).
If ci and ci+1 are different on vertex vq then |Fi ∩ Fi+1| = min(|Fi|, |Fi+1|) − 1. Thus
|Fi ∩ Fi+1| ≥ 2 except possibly when ci, ci+1 differ on vertex vq and additionally either
i = 1 or i = N (the case |FN ∩F1|). Since c1 uses just colors 1, 2, the unique coloring that
differs from c1 only on vq must assign vq color 3. So either cN or c2 must differ from c1 on
a vertex other than vq . Thus at least one of |FN ∩ F1| and |F1 ∩ F2| will have 2 elements
and we can select an edge from each of ĉN ĉ1 and ĉ1ĉ2 that use different vertices in ĉ1.
Part III Trees using exactly 3 colors. A more involved proof is necessary for the case
when exactly 3 colors are used to color the tree. The proof is similar to that used by
MacGillvray and Choo in [2] to show C3(T ) is Hamiltonian for T not a star.
The proof is by induction on n = |V (T )|. Observe that for n ≤ 4, Canπ3 (T ) has a
Hamilton path. If T is a star, then Canπ3 (T ) has a Hamilton cycle by part I of the proof.
Otherwise, consider T ′ = T − {u, v} for some pair of leaves u, v, that do not have a
common neighbor. Such a pair must exist since T is not a star. If n > 4 the inductive
hypothesis gives that Canπ3 (T
′) has a Hamilton path c0, c1, . . . , cN−1.
Order the vertices of T with u, v last and so the order on T ′ is the one that gave
the Hamilton path c0, c1, . . . , cN−1. Let ĉi be the induced subgraph of Canπ3 (T ) whose
vertex set is the set of canonical 3-colorings of T that agree with ci on T ′. Clearly, ĉi
is a 4 cycle. The Hamilton cycle in Canπ3 (T ) will be constructed so it passes through
ĉ0, ĉ1, . . . ĉN−2, ĉN−1, ĉN−2, . . . ĉ2, ĉ1, ĉ0, in that order.
Let u0 and v0 denote the unique vertices adjacent to u, v ∈ T respectively. Let [ĉi, ĉi+1]
denote the subgraph consisting of the edges between ĉi and ĉi+1 in Canπ3 (T ) and the ver-
tices they are incident to. Recall that the colorings ci and ci+1 differ on exactly one vertex,
say x. There are 3 cases.
Case 1: x 6∈ {u0, v0}. Then there is a perfect matching between the 4 vertices in ĉi and
ĉi+1.
Case 2: x = u0. In this case there will be two edges between the vertices in ĉi and
ĉi+1. We describe the subgraph induced by the vertices in ĉi ∪ ĉi+1 in this case. Without
loss of generality, let the 2 colors available for use on u be {1, 3} in ĉi and {2, 3} in ĉi+1;
and the two colors for use on v be {1, 2} in both ĉi and ĉi+1. The 8 vertices in ĉi ∪ ĉi+1
are labeled by the colorings on T ′ (ci or ci+1) followed by the color on u and the color
on v. Thus the 10 edges will be {(ci11, ci12), (ci12, ci32), (ci32, ci31), (ci31, ci11)} in
ĉi, {(ci+131, ci+121), (ci+121, ci+122), (ci+122, ci+132), (ci+132, ci+131)} in ĉi+1, and
{(ci32, ci+132), (ci31, ci+131)} in E([ĉi, ĉi+1]).
154 Ars Math. Contemp. 5 (2012) 149–157
Case 3: x = v0 is similar. Again there are exactly two edges in E([ĉi, ĉi+1]). The
vertices they are incident to in ĉi are adjacent, and the vertices in ĉi+1 are adjacent.
Next, for each i we construct the two pieces of the cycle Pi, Qi that use all vertices of ĉi
such that P0P1P2 . . . PN−1QN−1 . . . Q2Q1 is the desired Hamilton cycle.
Step 0. Construct P0. Say the 4-cycle ĉ0 is α0, β0, γ0, δ0. Assume without loss of gen-
erality that α0, δ0 are adjacent to vertices in ĉ1, call these vertices in ĉ1 β1, γ1 respectively.
Then define P0 = α0, β0, γ0, δ0.
Step i. βi, γi have been defined previously as vertices in ĉi adjacent to vertices in ĉi−1.
There are several cases. In each case Pi will begin with γi and Qi will end with βi.
Case uu. Suppose the colorings ci−1, ci, ci+1 differ only by color change on u0 (re-
spectively, only on v0). In this case u (respectively, v) must take on all 3 colors, so that
V ([ĉi−1, ĉi])∩V ([ĉi, ĉi+1]) = ∅. Label αi, δi such that the 4-cycle that is ĉi is αi, βi, γi, δi.
Now αi, δi are the vertices adjacent to vertices in ĉi+1, which we now label βi+1, γi+1 re-
spectively. Define Pi = γi, δi and Qi = αi, βi. Figure 3(Top) gives an example of this
case.
Case uv. Suppose the colorings ci−1, ci, ci+1 differ by color change first on u0 and
then on v0. In this case V ([ĉi−1, ĉi]) ∪ V ([ĉi, ĉi+1]) use only three different vertices of ĉi.
If V ([ĉi−1, ĉi]) ∩ V ([ĉi, ĉi+1]) = γi then label the rest of the 4 cycle in ĉi so that δi is also
adjacent to a vertex in ĉi+1. Next label the vertices adjacent to γi, δi in ĉi+1 as βi+1, γi+1
respectively. Now define Pi = γi and Qi = δi, αi, βi. Figure 3(Bottom) gives an example
of this case.
Similarly, if V ([ĉi−1, ĉi]) ∩ V ([ĉi, ĉi+1]) = βi then label so that βi+1, γi+1 ∈ ĉi+1 are
the vertices adjacent to αi, βi respectively. Now define Pi = γi, δi, αi and Qi = βi.
Case ux. Suppose the colorings ci−1, ci, ci+1 differ first by a color change on u0 and
then on some x 6∈ {u0, v0}. Label αi, δi such that the 4-cycle that is ĉi is αi, βi, γi, δi.
Now αi, δi are adjacent to vertices in ĉi+1, which we now label βi+1, γi+1 respectively.
Define Pi = γi, δi and Qi = αi, βi.
Case xx. Suppose the colorings ci−1, ci, ci+1 differ only on vertice(s) not {u0, v0}. As
in the other cases, label αi, δi such that the 4-cycle that is ĉi is αi, βi, γi, δi. Now αi, δi are
adjacent to vertices in ĉi+1, which we now label βi+1, γi+1 respectively. Define Pi = γi, δi
and Qi = αi, βi.
Cases vu, xu, xv and vx are similar to those above.
4 Cycles
Another simple class of graphs to consider is Cn, the cycle on n vertices. We prove that
there exists an order such that Canπk (Cn) is connected for most n, k. While lengthy com-
puter calculations indicate Canπk (Cn) is Hamiltonian for n > 5, a concise proof is elusive.
Theorem 4.1. For Cn a cycle with n ≥ 3, vertices, and k ≥ 4 colors, there is an order π
of the vertices such that Canπk (Cn) is connected. Further, Can
π
3 (C4) and Can
π
3 (C5) are
connected for some π but Canπ3 (Cn) is disconnected for all π, for n > 5.
Proof. The proof is in two parts.
R. Haas: The canonical coloring graph of trees and cycles 155
ĉi−1 ĉi ĉi+1r r r r r r
r r r r r r
11 31
αi−1
31
βi
21
αi
21
βi+1
11
12 32
δi−1
32
γi
22
δi
22
γi+1
12
-
Pi
Qi
ĉi−1 ĉi ĉi+1r r r r r r
r r r r r r
11 31
αi−1
31
βi
21
αi
32
βi+1
33
12 32
δi−1
32
γi
22
δi
22
γi+1
23
-

Pi
Qi
Figure 3: Both figures show possible subgraphs induced by ĉi−1 ∪ ĉi ∪ ĉi+1. The numbers
(eg 12) give colors on u, v in the underlying graph. The subscripted letters correspond to
the notation developed in Step 0 and i of the proof. The dashed lines represent the paths Pi
and Qi. Top: The colorings ci−1, ci, ci+1 differ only by color change on u0. Bottom: The
colorings ci−1, ci, ci+1 differ by color change first on u0 and then v0.
156 Ars Math. Contemp. 5 (2012) 149–157
Part I: k = 3. It is easy to check that Canπ3 (C4) and Can
π
3 (C5) are connected for
many π (for example, let the cycle be (1, 2, 3, 4, 5) and color in the order given by π =
(1, 4, 2, 3, 5)). We show that for n > 5 Canπ3 (Cn) is disconnected. In a 3-colored cycle,
the only vertices that can change color are those whose neighbors in the cycle are both the
same color. Thus, for n > 5, when n = 3t the coloring [1, 2, 3, 1, 2, 3, . . . , 1, 2, 3] (where
the vertices are listed in the usual order), will be an isolated vertex under any ordering π.
For n = 3t + 2 consider first C3(Cn), all colorings of Cn in the standard order. Define L
to be the set of colorings which for some choice of initial vertex are contiguous substrings
of 1, 2, 3, 1, 2, 3, . . . 1, 2, 3. Colorings in L are only adjacent to other colorings in L. For
example, consider [1, 2, 3, 1, 2, 3, . . . , 1, 2, 3, 1, 2] in the usual order. The only colorings
this is adjacent to in C3(Cn), whether canonical or not, are [3, 2, 3, 1, 2, 3, . . . , 1, 2, 3, 1, 2]
and [1, 2, 3, 1, 2, 3, . . . , 1, 2, 3, 1,3], where the bolded number is the changed color. Each
of these is also a coloring in L, the first by considering the second vertex as the “initial ver-
tex” and the second by considering the last vertex as the initial vertex. Thus any coloring
not in L must be in a different connected component of C3(Cn). Since at least one coloring
of L is in Canπ3 (C3t+2) for any ordering π, Can
π
3 (C3t+2) must also be disconnected.
For n = 3t + 1 things are slightly more complex. Again consider first the regu-
lar coloring graph C3(Cn). Define M to be the set of colorings consisting two disjoint
contiguous substrings of [1, 2, 3, 1, 2, 3, . . . , 1, 2, 3]. Colorings in M are only adjacent to
other such colorings in C3(Cn). Without loss of generality suppose the substrings meet as
follow [. . . , 3, 1, 2, 3, 2, 3, 1, . . . ]. This is only adjacent to [. . . , 3, 1, 2,1, 2, 3, 1, . . . ] and
[. . . , 3, 1, 2, 3,1, 3, 1, . . . ] and two more similar colorings at the other end of where the two
strings meet. In each case the new coloring simply increases the length of one substring
of [1, 2, 3, 1, 2, 3, 1, 2, 3, . . . , 1, 2, 3] and decreases the other. Under any ordering π there
will be at least one coloring of type M when considered in the usual order, and at least one
coloring not of type M , so Canπ3 (C3t+1) must also be disconnected.
Part II: k ≥ 4 colors. For k ≥ 4 colors, the cases n = 3, 4 are easily verified. For n ≥ 5,
Theorem 3.1 gives a method for finding a Hamilton cycle in Canπk (Pn−1), where Pn is the
path on n vertices. Let the colorings of Pn−1 be c1, c2, . . . cN listed in the order they give
a Hamilton cycle and so that c1 is the unique coloring that uses only 2 colors.
For any i, ci can be extended to a coloring of Cn by coloring vn. Let Fi be the set of
colors for vn compatible with ci and let ĉi be the set of colorings ofCn. All colorings ofCn
are obtained this way. Vertex vn can receive any color already used except the ones used on
its neighbors v1 and vn−1. If only r < k colors have been used in ci then color r+1 can be
used as well. Thus |Fi| ≥ 2 for i > 1. Consider first the case where i 6= 1, N . If ci and ci+1
are the same on vertices v1, vn−1 then |Fi ∩ Fi+1| = min(|Fi|, |Fi+1|) ≥ 2. If ci and ci+1
are different on one of the vertices v1, vn−1 then |Fi ∩Fi+1| = min(|Fi|, |Fi+1|)− 1 ≥ 1.
For i = 1 or i = N consider the cases that n is odd or even separately. If n − 1
is odd the Hamilton cycle constructed on Canπk (Pn−1) will contain the segment con-
sisting of colorings cN = [1, 2, 1, 2, 1, . . . , 1, 3, 1]; c1 = [1, 2, 1, 2, 1, . . . , 1, 2, 1]; c2 =
[1, 2, 1, 2, 1, . . . , 1, 2, 3]. Here |FN ∩ F1| = |{2, 3}| = 2 > 0; and |F1 ∩ F2| = |{2}| > 0.
So there is at least one edge between ĉN and ĉ1 and also between ĉ1 and ĉ2. If n − 1 is
even the Hamilton cycle constructed on Canπk (Pn−1) will contain the the segment con-
sisting of colorings cN = [1, 2, 1, 2, 1, . . . , 2, 1, 3]; c1 = [1, 2, 1, 2, 1, . . . , 2, 1, 2]; c2 =
[1, 2, 1, 2, 1, . . . , 2, 3, 2]. In this case FN = {2, 4}; F1 = {3}, F2 = {3, 4} so FN∩F1 = ∅.
But since F1 ∩ F2 = {3} there is one edge between ĉ1 and ĉ2 and Canπk (Cn) is con-
R. Haas: The canonical coloring graph of trees and cycles 157
nected.
Note that the method in this proof is not enough to guarantee a Hamilton Cycle in
Canπk (Cn) as it is possible that |Fi−1 ∩ Fi| = |Fi ∩ Fi+1| = 1, and each of |Fi−1| =
|Fi| = |Fi+1| = 2. This occurs when each of ci−1, ci, ci+1 uses exactly colors {1, 2, 3}
and the colors on (v1, vn−1) are (1, 3), (1, 2), (3, 2) in colorings ci−1, ci, ci+1 respectively.
In this case Fi−1 ∩ Fi = Fi ∩ Fi+1 = {4}, while the possibilities for vn are Fi−1 =
{2, 4}, Fi = {3, 4}, Fi+1 = {1, 4}.
It would be interesting to have broad results paralleling Theorems 1.2 and 1.3 for the
cannonical coloring graph. Indeed, for all G does there exists k, π such that Canπk (G)
is connected? In a forthcoming paper the author shows connectivity for some classes of
graphs (see [4]).
The author wishes to thank the anonymous referees for their useful suggestions.
References
[1] L. Cereceda, J. van den Heuvel and M. Johnson, Connectedness of the graph of vertex-
colourings, Discrete Math. 308 (2008), 913–919.
[2] K. Choo and G. MacGillivray, Gray code numbers for graphs, Ars Math. Contemp. 4 (2011)
125–139.
[3] 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.
[4] R. Haas and G. MacGillivray, Some results on the canonical coloring graph, in preparation.
[5] 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.
[6] M. Molloy, The Glauber dynamics on colorings of a graph with high girth and maximum de-
gree, SIAM J. Comput. 33 (2004), 721–73.
[7] A. D. Sokal, A personal list of unsolved problems concerning lattice gases and antiferromag-
netic Potts models. Inhomogeneous random systems, (Cergy-Pontoise, 2000), Markov Process.
Related Fields 7 (2001), 21–38.
[8] E. Vigoda, Improved bounds for sampling colorings, Probabilistic techniques in equilibrium
and nonequilibrium statistical physics, J. Math. Phys. 41 (2000), 1555–1569.