ars mathematica contemporanea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 155-165
Uniquely colorable Cayley graphs
Walter Klotz
Institut fur Mathematik, Technische Universität Clausthal 38678 Clausthal-Zellerfeld, Germany
Torsten Sander
Fakultat Informatik, Ostfalia Hochschule für angewandte Wissenschaften 38302 Wolfenbuttel, Germany
Received 24 June 2015, accepted 5 January 2016, published online 15 November 2016
It is shown that the chromatic number x(G) = k of a uniquely colorable Cayley graph G over a group r is a divisor of |r | = n. Each color class in a k-coloring of G is a coset of a subgroup of order n/k of r. Moreover, it is proved that (k - 1)n is a sharp lower bound for the number of edges of a uniquely k-colorable, noncomplete Cayley graph over an abelian group of order n. Finally, we present constructions of uniquely colorable Cayley graphs by graph products.
Keywords: Vertex coloring, color classes, Cayley graph. Math. Subj. Class.: 05C15, 05C25
1 Introduction
A proper k-coloring of an undirected graph G = (V, E) with vertex set V = V(G) and edge set E = E (G) is a map f : V ^ C from V into a set C with |C | = k elements ('colors') such that any two adjacent vertices are assigned different colors. If not otherwise stated a k-coloring is always understood to be a proper k-coloring. A graph G is k-colorable if it admits a k-coloring. The chromatic number x(G) is the smallest number k for which G is k-colorable. An optimal coloring of G is a x(G)-coloring of G. The color class of the coloring f : V ^ C with respect to color c G C consists of all vertices x G V with f (x) = c. If f is a k-coloring of G, then the color classes of f constitute a partition of V into at most k disjoint stable sets which means that any two elements of these sets are nonadjacent. The graph G is uniquely colorable if every optimal coloring of G induces the
E-mail addresses: klotz@math.tu-clausthal.de (Walter Klotz), t.sander@ostfalia.de (Torsten Sander) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
156
Ars Math. Contemp. 12 (2017) 111-126
same partition into color classes. If G is uniquely colorable, then we mean by the color classes of G the color classes of an optimal coloring of G.
Let us point out some previous work on uniquely colorable graphs. Harary et al. [11] construct new ones from given uniquely colorable graphs. Bollobas [4] presents a lower bound for the minimal degree ¿(G) which forces G to be uniquely colorable. Hillar and Windfeldt [13] give an algebraic characterization of uniquely k-colorable graphs, which partly originates in ideas of Lovasz [16] and Bayer [3]. They also apply commutative algebra to develop an algorithm for recognizing unique colorability. Xu [19] establishes a sharp lower bound for the number of edges of a uniquely k-colorable graph on n vertices:
|E| > (k - 1)n - Q .	(1.1)
Daneshgar [7] and Daneshgar, Naserasr [8] concentrate on cliques in uniquely colorable graphs. Special classes of uniquely colorable graphs are investigated by Akbari et al. [1], Chao and Chen [5], Chartrand and Geller [6].
The Cayley graph G = Cay(r, S) over the finite (multiplicative) group r with shift set (or symbol) S C r has vertex set V = V(G) = r and edge set
E = E(G) = {{x,y} : x,y G r,xy-1 G S}.
To avoid loops we demand that the unit element e G r is not in S. To make G undirected we require that S is self-inverse, S-1 = S, which means that s G S always implies s-1 G S. For general properties of Cayley graphs we refer to Godsil and Royle [9]. Circulant graphs are Cayley graphs over cyclic groups. We represent the cyclic group of order n by the additive group Zn of integers modulo n, Zn = {0,1,..., n - 1}. A well-known circulant graph is the unitary Cayley graph
Xn = Cay(Z„, Un) with U„ = {x G Zn : gcd(x, n) = 1}.
Here gcd(x, n) denotes the greatest common divisor of x and n and Un is the set of multiplicative units of Zn considered as a ring. In [15] we proved for n > 1 that x(Xn) = p, where p is a smallest prime divisor of n. Basic and Ilic [2] remarked in passing that Xn is uniquely p-colorable. This remark encouraged us to look closer at uniquely colorable Cayley graphs in general.
In this paper we show that the chromatic number x(G) = k of a uniquely colorable Cayley graph G over a group r is a divisor of the number of elements |r| = n of r. Each color class of G is a coset of some subgroup of order n/k of r. For a uniquely colorable, noncomplete Cayley graph over an abelian group the estimate (1.1) on its number of edges can be improved to |E| > (k - 1)n. For every divisor k of n, 1 < k < n, we construct a uniquely k-colorable circulant graph on n vertices with the minimal number of (k - 1)n edges. In the final section, extending a result of Greenwell and Lovasz [10], we present a general method for constructing uniquely colorable graphs by graph products, which can especially be applied to Cayley graphs.
2 Necessary conditions
A graph G = (V, E) is transitive if for any two vertices x, y G V there is an automorphism t of G with t(x) = y. Transitive graphs are regular. We call G weakly transitive if we require the existence of an automorphism t of G with t (x) = y only for adjacent vertices x and y.
W Klotz and T. Sander: Uniquely colorable Cayley graphs
157
Lemma 2.1. Let the graph G = (V, E) be weakly transitive und uniqely k-colorable. Then x(G) = k is a divisor of | V| = n and every color class of G has n/k elements.
Proof. We may assume k > 1. Let Ci, C2 be an arbitrary pair of color classes of G. Since x(G) = k there exists a pair x, y of adjacent vertices x G C and y G C2. As G is weakly transitive we know that there is an automorphism t of G with t(x) = y. Every automorphism of a uniquely colorable graph G maps each color class of G to another color class of G. Therefore, x G C1, y G C2 and t(x) = y imply t(C1) = C2 and |C1| = |C2|. Every color class C of G has the same number of |C| elements. As the color classes partition the vertex set V into k disjoint sets of equal size |C|, we have |V| = n = k|C|, which proves the lemma.	□
Let G = Cay(r, S) be a Cayley graph. Define the bijection Ta : r ^ r for a G r by
Ta (x) = xa. We verify for x, y G r:
x, y adjacent in G ^ xy-1 G S ^ (xa)(ya)-1 G S ^ Ta(x),Ta(y) adjacent in G.
For a = x-1y we have Ta(x) = y. This shows that H(r) = {Ta : a G r} is a subgroup of the automorphism group Aut(G) that operates transitively on the vertices of G. As Cayley graphs are transitive, Lemma 2.1 can especially be applied to Cayley graphs.
Theorem 2.2. For a uniquely colorable Cayley graph G = Cay(r, S) the following statements are true.
1.	The chromatic number x(G) = k divides the number |V(G)| = |r | = n of vertices of G.
2.	Every color class C of G is a left coset of a subgroup U (C) C r of order |U (C) | =
n k'
3.	For any two distinct color classes C1 and C2 of G there exists an element y G r such that U(C2) = 7U(C1)y-1. If r is abelian, then every color class C of G has the same subgroup U(C).
Proof. 1. This is a consequence of Lemma 2.1.
2. Suppose that C = {a1,..., ar }, r = n/k, is a color class of G. Define
U = U(C) = {a-1aj : i,j G{1,...,r}}.
We prove that U is a subgroup of r.
The unit element e = a-1aj belongs to U. For x = a-1aj G U we have x-1 = a—1ai G U. Assume that x = a-1aj G U and y = a-1at G U. We are going to show xy G U. The automorphism tx of G maps a4 to aj, Tx(aj) = a4x = aj. From the unique colorability of G we conclude tx(C) = C and analogously Ty(C) = C. For arbitrary Z G C we have
Tx(Z) = Zx = Z1 G c, Ty (Z1) = Z1y = Zxy = Z2 G C, xy = Z-1Z2 G U.
Next, we show C = a1U, the left coset of U represented by a1. For every a4 G C we have aj = a1 (a-1ai) G a1U, which implies C C a1U. Suppose
z G a1U, z = a1a—1aj- = a1x, x = a— 1aj- for some i, j G {1,..., r}.
158
Ars Math. Contemp. 12 (2017) 111-126
As above we see tx(C) = C. Therefore, z = a1x = rx(ai) G C, C = a\U.
3. Let C1 = aU1 and C2 = bU2 be different color classes of G, U1 U2 = U(C2). For the automorphism Td of G with d = a-1b we have Td(a) unique colorability of G implies Td(C1) = C2, hence
C2 = C1d, bU2 = aU1 a-1b
and therefore
U2 = CU1C-1 with Z = b-1a. If r is abelian, we conclude U2 = U1.	□
Corollary 2.3. If G = Cay(Zn, S) is a uniquely colorable circulant graph, then x(G) = k is a divisor of n. The color classes of G are the residue classes modulo k in Zn. If S is extended by elements s' G Zn, s' ^ 0 modulo k, to a self-inverse set S', then G' = Cay(Zn, S') is also a uniquely colorable graph with x(G') = k.
Proof. According to Theorem 2.2, the color classes of G are the cosets of a subgroup U C Zn, |U| = n/k. The (additive) cyclic group Zn has exactly one subgroup of order n/k that is (k) = {0, k,..., (n/k — 1)k}, the cyclic subgroup generated by k. The cosets of (k) are the residue classes modulo k in Zn. The graph G' = Cay(Zn, S') is constructed from G by adding edges between different color classes. So the graph remains uniquely colorable with the same chromatic number.	□
Problem 2.4. Is there a uniquely colorable Cayley graph over a nonabelian group such that different color classes are left cosets of different subgroups?
Theorem 2.5. Let G = Cay(r, S) be a uniquely colorable Cayley graph over the abelian group r, |r| = n, x(G) = k < n. Then we have:
The subgraph of G induced by any two color classes of G is uniquely colorable and regular of degree l > 2. Moreover, |E (G)| > (k — 1)n. This bound is sharp.
Proof. The subgraph induced by any color classes of G must be uniquely colorable because otherwise G would not have this property. Consider arbitrary different color classes C and D of G. According to Theorem 2.2(3) they are cosets C = aU, D = bU of the same subgroup U = {u1,..., ur } C r, r = n/k. Without loss of generality let au1 be a vertex of maximum degree l in the subgraph G1 = G(C U D) induced by C U D in G. The neighbors of au1 in G1 must lie in bU. Let these be bu4l,..., bujj. For u G U we apply the automorphism tu of G defined by Tu(x) = xu to au1 and its neighbors in G1 and conclude:
au1u G aU is adjacent to buil u,..., bu^ u G bU for every u G U.
As au1u runs through all elements of aU for u G U, we see that all vertices in aU must have the same degree l in G1. The same holds for the vertices of bU since the r vertices of bU have rl edges in G1 and the maximum degree of G1 is l.
It is easy to see (cf. Theorem 1 in [11]) that the subgraph G1 = G(C U D) induced by any two color classes C, D of G must be connected. This implies
= U (C1), = b. The
nn
lT = |E (G1)|>|V (G1 )| — 1 = 2 - — 1
W Klotz and T. Sander: Uniquely colorable Cayley graphs
159
so that
l > 2 - k > 1.
n
As l is an integer we have l > 2. This implies for |S|, the degree of regularity of G, |S| > 2(k - 1). Finally, we estimate the number of edges of G:
|E(G)| = 2|S|n > (k - 1)n.
Examples in the next section (see Corollary 3.4) will show that this bound is sharp. □
3 Uniquely colorable Cayley graphs with few edges
For the next theorem recall that the clique number "(G) of a graph G is the largest number of vertices in a complete subgraph of G. The clique number "(G) of the complementary graph G of G is also known as the independence number or stability number of G.
Theorem 3.1. Let U be a subgroup of the (additive) abelian group r, |U | = | r | /k, k > 1 a divisor of |r|. Moreover, let jri,..., rk} be a system of distinct representatives of the cosets of U in r. Define
S = {r - rj : i, j e {1,..., k}, i = j} and G = Cay(r, S).
Then we have:
1.	x(G) = "(G) = k.
2.	x(G) = "(G) = JT.
3.	The cosets of U in r are the color classes of an optimal coloring of G.
Proof. From the definition of the representatives r1,..., rk we deduce Sn U = 0. Suppose that x, y belong to the same coset rj + U, 1 < i < k. Then we can find elements ui, u2 e U such that x = rj + u1 and y = r + u2. Now x - y = u1 - u2 e U implies x - y e S, which means that x and y are not adjacent in G. The cosets of U partition the vertex set r of G into k stable sets, i.e. sets of pairwise nonadjacent vertices. So we have
"(G) < x(G) < k.
On the other hand r1,..., rk induce a clique of size k in G. This proves claims 1 and 3.
Let U = {u1,..., ut}, t = |r|/k. The sets
Kj = {rj + uj : i = 1,..., k}, 1 < j < t,
induce cliques of size k in G, and therefore stable sets of size k in G. To show that these sets are pairwise disjoint, we assume x e Kj1 nKj2 for j1 = j2. We can find i1,i2 e {1,..., k} such that
x rii H- uji ri2 ++ uj2 .
Hence,
rjl rj2 uj2 uji e U.
160
Ars Math. Contemp. 12 (2017) 111-126
From S n U = 0 we deduce i\ = i2, which implies j = j2 contrary to our assumption. The sets Kj, 1 < j < t, constitute a partition of the vertex set r of G into t = |r|/k stable sets of G. Therefore, we have
"(G) < X(G)	.
Finally, claim 2 follows from the fact that every coset of U induces a clique of size t = |r|/k in G.	□
Theorem 3.1 gives a first impression of what symbol sets may potentially yield uniquely colorable Cayley graphs. The next example, however, shows that the symbol set structure mentioned there is not sufficient in general for unique colorability.
Example 3.2. We consider the integers modulo 12, r = Z12 = {0,1,..., 11}. Let U = (4) = {0,4, 8} be the cyclic subgroup of Z12 generated by 4. Then we have k = |r|/|U| = 4 and {r1, r2, r3, r4} = {0,1,6,7} as a system of distinct representatives for the cosets of U. We define
S = {r - rj : i,j € {1,..., 4}, i = j} = {1, 5, 6, 7,11} and G = Cay(r,S). According to Theorem 3.1 the cosets of U in r,
{0, 4, 8}, {1, 5, 9}, {2, 6,10}, {3, 7,11},
are the color classes of an optimal coloring of G. But there is another partition of Z12 into four stable sets of G:
{0, 2,4}, {1, 3, 5}, {6, 8,10}, {7, 9,11}. Therefore, G is not uniquely colorable.
A more careful choice of the system of representatives will improve the situation.
Theorem 3.3. Let k be a divisor of n, 1 < k < n,
Sk,n = {1, 2,..., k — 1} U {n — 1, n — 2,..., n — (k — 1)}, and Gk,n = Cay(Zn, Sk,n). Then the circulant graph Gk n is uniquely colorable with
x(Gk,n) = w(Gfc,n) = k and x(Gfc,„) = w(Gfc,n) = p	(3.1)
The residue classes modulo k in Zn are the maximal stable sets of Gk,n and the color classes of an optimal coloring of Gk,n.
Proof. The integers ri =0, r2 = 1,..., rk = k - 1 constitute a system of distinct representatives for the cosets of the subgroup U = (k) generated by k in Zn. Modulo n we have:
Sk,n = {ri - rj : i, j G {1, 2, .. . ,k}, i = j}.
Now Theorem 3.1 implies (3.1) and the fact that the cosets of U, i.e. the residue classes modulo k in Zn, are the color classes of an optimal coloring of Gk n. Let M be a stable
W Klotz and T. Sander: Uniquely colorable Cayley graphs
161
set with a maximal number of vertices in Gk,n. We have |M| = n/k by (3.1). For every x G M the consecutive integers x +1,..., x + k - 1 (modulo n) are adjacent to x and therefore not in M. This implies that M is the residue class x + (k) in Zn.
Let F be an optimal coloring of G„jfc, i.e. a coloring of the vertices of Gfcj„ with k colors. Every color class of F must be a maximal stable set of G„jfc with n/k elements. We have just shown that these sets are the cosets of U = (k) in Zn. Therefore, Gfcj„ is uniquely colorable.	□
The graph Gfcj„ = Cay(Zn, Sk,n) is regular of degree |Sk,n| = 2(k - 1). This implies |E(Gfcj„)| = (k - 1)n. Hence we immediately obtain:
Corollary 3.4. For every divisor k of n, 1 < k < n, the graph Gk,n defined in Theorem 3.3 is a uniquely k-colorable, circulant graph with n vertices and the minimal number of
|E(Gfcj„)| = (k - 1)n edges.
Example 3.5. Let Xn = Cay(Zn, Un) be the unitary Cayley graph on n vertices, Un = {x G Zn : gcd(x, n) = 1}. Suppose that p is the smallest prime divisor of n, 1 < p < n. According to Theorem 3.3 we define
SPtn = {1, 2,... ,p - 1} U {n - 1, n - 2,..., n - (p - 1)} and GPj„ = Cay(Z„, Sp,n).
Then Gp,n is uniquely colorable and x(Gp,n) = x(Xn) = p. The unitary Cayley graph Xn results from Gp,n by adding additional edges between different color classes of Gp,n. So Xn and Gp,n are both uniquely colorable with the same color classes.
Problem 3.6. Is necessarily x(G) = w(G) for every circulant uniquely colorable Cayley graph?
4 Constructing uniquely colorable graphs by graph products
The direct product X x Y of graphs X and Y has as its vertex set the cartesian product V(X) x V(Y). Vertices (xi, yi), (x2, y2) of X x Y are adjacent if xi is adjacent to x2 in X and y1 is adjacent to y2 in Y .If X = Cay(r1, S1) and Y = Cay(r2, S2) are Cayley graphs, then X x Y is a Cayley graph Cay(r, S) over the direct product r = r1 x r2 with shift set S = S1 x S2. A product X x Y of connected graphs is connected if both factors have at least two vertices and at least one factor is not bipartite (see [14]). Every proper n-coloring f : V (X) ^ Zn of X induces a proper n-coloring F : V (X) x V(Y) ^ Zn of X x Y by F(x, y) = f (x) for every x G V(X), y G V(y). As the same is true for Y instead of X, we immediately see
x(X x Y) < min{x(X),x(Y)}.
A famous conjecture of Hedetniemi ([12], [17]) states that always equality occurs. We denote by 2K2 the graph consisting of two disjoint edges. A graph X is 2K2-free if it has no induced subgraph 2K2. D. Turzik [18] showed that Hedetniemi's conjecture is true if one of the factors is 2K2-free.
Lemma 4.1. Let the graph X be 2K2-free and let c : V(X) x V(Y) ^ Zn be a proper n-coloring of X x Y. For y G V (Y) define the map cy : V(X) ^ Zn by
cy (x) = c(x, y) for every x G V(X).
If every cy, y G V (Y), is an improper coloring of X, then x(Y) < n.
162
Ars Math. Contemp. 12 (2017) 111-126
Proof. The map cy is an improper coloring of X means that there are adjacent vertices xi, x2 of X such that cy(xi) = cy(x2). Let be the least value cy(xi) such that there are adjacent vertices x1, x2 of X with cy (x1) = cy(x2). We show that ^ is a proper n-coloring of Y.
Let y1, y2 be adjacent vertices of Y. Assume ^(y1) = y>(y2). Then we find two pairs x1, x2 and x3, x4 of adjacent vertices in X such that
cyi (x1) = cyi (x2 ) = ^(y1) = ^(y2) = cy2 (x3) = cy2 (x4),
c(x1,y1) = c(x2,y1) = c(x3,y2) = c(x4,y2).	(4.1)
As x1 , . . . , x4 do not induce a subgraph 2K2 in X, either {x1, x2} n {x3, x4} = D = 0 or D = 0 and there is an edge between {x1, x2} and {x3, x4}. Suppose e.g. D = 0 and x1, x3 are adjacent. Then (x1, y1) and (x3, y2) are adjacent vertices of X x Y. But now c(x1, y1) = c(x3, y2) in (4.1) contradicts the fact that c is a proper coloring of X x Y. Similarly, the other cases lead to a contradiction.	□
The following theorem extends a result of Greenwell and Lovasz [10].
Theorem 4.2. Let the graph X be uniquely n-colorable and 2K2-free. If Y is a connected graph with chromatic number x(Y) > n, then X x Y is uniquely n-colorable.
Proof. We know x(X x Y) = m < x(X) = n. Let c : V(X) x V(Y) ^ Zm be an arbitrary proper m-coloring of X x Y. For y G Y define cy : V (X) ^ Zm by
cy (x) = c(x, y) for every x G V(X).
If cy is an improper m-coloring of X for every y G Y, then Lemma 2.1 implies x(Y) < m < n contradicting x(Y) > n. We conclude that there is a vertex y of Y such that cy is a proper m-coloring of X. Moreover, m < n = x(X) implies m = n. Let u be any neighbor of y in Y. Assume that there is a vertex x1 in X such that cu(x1) = cy(x1). As cy is a proper n-coloring of the uniquely n-colorable graph X, all n colors except cy (x1) appear in the range of cy at the neighbors of x1 . In particular, we find a neighbor x2 of x1 with cy(x2) = cu(x1), c(x2, y) = c(x1,u). But this is impossible, because (x2,y) is adjacent to (x1, u) in X x Y and c is a proper coloring of this graph. Therefore, we have
cu(x) = cy(x) for every x G V(X).
We may repeat the above argument for every neighbor of u. Continuing this way we reach every vertex in the connected graph Y and achieve the following result:
c(x, y1) = c(x, y2) for every y1, y2 G V(Y) and every x G V(X).
This implies that the color classes C1,..., Cn of the arbitrary n-coloring c of X x Y are given by the uniquely determined color classes D1,..., Dn of X,
C = Dj x Y, for i = 1,..., n.
This means that X x Y is uniquely n-colorable.	□
In the following subsections we present some graph candidates for the application of Theorem 4.2.
W Klotz and T. Sander: Uniquely colorable Cayley graphs
163
4.1 Complete multipartite graphs
We call a graph X a complete m-partite graph if its vertex set V(X) can be partitioned into m nonempty, disjoint subsets ('color classes') such that each vertex is adjacent to every vertex which is not in his own class. Obviously, these graphs are uniquely m-colorable and 2K2-free. If a complete m-partite graph is regular, then all color classes must have the same size k. Such a graph can be represented as a Cayley graph over Zm x Z^.
Corollary 4.3. Let X, be a complete m,-partite graph for i = 1,... ,r, r > 2, and 2 < mi < m2... < mr. Then X = Xi x X2 x ... x Xr has chromatic number x(X) = m1. The graph X is uniquely m1-colorable if and only if m1 < m2.
Proof. We have x(X) < min{m1,..., mr} = m1. If we take one vertex from each color class of Xj we get a clique Q, of size m, in Xj. Assume that Q, has vertex set {1, 2,..., m,}. Then the tuples (a, a,..., a) with the r-fold entry a G {1, 2,..., m1} define a clique of size m1 in X. Thus we see x(X) = m1.
If m1 < m2 we set Y = X2 x ... x Xr. This graph is connected with x(Y) = m2 > m1 = x(X1). Therefore, we may apply Theorem 4.2 to the product X1 x Y and conclude that it is uniquely m1 -colorable.
If m1 = m2 = m, let f1 be an m-coloring of X1 and f2 be an m-coloring of X2. The colorings of X induced by f1 and by f2 are distinct optimal colorings of X.	□
4.2 Complementary graphs of compass graphs
0
14
13
12
9
Figure 1
4
5
The compass graph CS(k, P) is regular of degree 3 and has n = 6k vertices, k > 2. The vertices 0,1,..., n - 1 are arranged in this order along a hamiltonian cycle. Every vertex x divisible by 3 forms a triangle with the adjacent vertices x ± 1 mod n. By P we denote a partition of Zm = {0,1,..., m - 1}, m = 2k, in 2-element subsets which do not
165
Ars Math. Contemp. 12 (2017) 111-126
consist of two consecutive integers modulo m. For every {a, b} e P we connect the vertices 3a and 3b by an edge. Figure 1 displays CS(3, P) with P = {{0,3}, {1,4}, {2,5}}.
Obviously, every compass graph CS(k,P) does not contain an induced cycle C4 of length 4. This means for the complementary graph CS(k, P) that it does not contain an induced 2K2. The maximal cliques of CS(k, P) are given by its triangles, which in CS(k, P) define the maximal stable sets. To achieve an optimal coloring of CS(k, P) we must take the sets of vertices {x, x — 1,x +1 mod n}, x = 0 mod 3, as color classes. The graph CS(k, P) is uniquely 2k-colorable. These graphs are candidates for the graph X in Theorem 4.2.
It seems to be difficult to decide generally which compass graphs are Cayley graphs. The graph in Figure 1 is the only Cayley compass graph with 18 vertices. Similarly, we found that there is a unique Cayley compass graph with 12, 24, 42, 48 or 54 vertices. But there is definitely no such graph with 30 or 36 vertices. Again, we found a compass graph with 60 vertices, which is a Cayley graph over the alternating group A5. But we do not know if it is unique.
Infinite sequences of 2K2-free, uniquely colorable Cayley graphs can be constructed by the following operations. The k-fold join, join(k, G), of a graph G consists of k disjoint copies G1,... ,Gk of G. For every i < j every vertex of Gj is connected by an edge to every vertex of Gj. Let the n x n-matrix A be an adjacency matrix of G and Jk the k x k-matrix with all entries equal to 1. The Kronecker product Jk x A is the (kn) x (kn)-matrix which results from Jk by replacing every entry by A. The k-fold clone, clone(k, G), is the graph with adjacency matrix Jk x A. We leave the proof of the following statement as an exercise for the reader.
Proposition 4.4. If the Cayley graph G is 2K2-free and uniquely colorable then join(k, G) and clone(k, G) are 2K2-free, uniquely colorable Cayley graphs for every integer k > 2.
References
[1]	S. Akbari, V. S. Mirrokni and B. S. Sadjad, Kr-free uniquely colorable graphs with minimum possible edges, J. Comb. Theory, Ser. B 82 (2001), 316-318.
[2]	M. Basic and A. Ilic, On the chromatic number of integral circulant graphs, Comput. Math. Appl. 60 (2010), 144-150.
[3]	D. Bayer, The division algorithm and the Hilbert scheme, PhD thesis, Harvard University, 1982.
[4]	B. Bollobas, Uniquely colorable graphs, J. Comb. Theory, Ser. B 25 (1978), 54-61.
[5]	C. Y. Chao and Z. Chen, On uniquely 3-colorable graphs, Discrete Math. 112 (1993), 21-27.
[6]	G. Chartrand and D. P. Geller, On uniquely colorable planar graphs, J. Comb. Theory 6 (1969), 271-278.
[7]	A. Daneshgar, Forcing structures and cliques in uniquely vertex colorable graphs, SIAM J. Discrete Math 14 (2001), 433-445.
[8]	A. Daneshgar and R. Naserasr, On small uniquely vertex colorable graphs and Xu's conjecture, Discrete Math. 223 (2000), 93-108.
[9]	C. Godsil and G. Royle, Algebraic graph theory, Graduate Texts in Mathematics, Vol 207, Springer, 2001.
[10] D. Greenwell and L. Lovasz, Applications of product coloring, Math. Acad. Sci. Hungar. 25 (1974), 335-340.
W Klotz and T. Sander: Uniquely colorable Cayley graphs
155
[11]	F. Harary, S. T. Hedetniemi and R. W. Robinson, Uniquely colorable graphs, J. Comb. Theory 6 (1969), 264-270.
[12]	S. Hedetniemi, Homomorphisms of graphs and automata, Technical report university of Michigan 03105-44-T (1966).
[13]	C. J. Hillar and T. Windfeldt, Algebraic characterization of uniquely vertex colorable graphs, J. Comb. Theory, Ser. B 98 (2008), 400-414.
[14]	R. Hammack, W. Imrich and S. KlavZar, Handbook of product graphs, 2nd ed., CRC Press, 2011.
[15]	W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Comb. 14 (2007), R45, 1-12.
[16]	L. Lovasz, Stable sets and polynomials, Discrete Math. 124 (1994), 137-153.
[17]	C. Tardif, Hedetniemi's conjecture 40 years later, Graph Th. Notes New YorkLIV(2008), 46-57.
[18]	D. Turzik, A note on direct product of graphs, Comment. Math. Univ. Carolin. 24 (1983), 461463.
[19]	S. Xu, The size of uniquely colorable graphs, J. Comb. Theory, Ser. B 50 (1990), 319-320.