# Uniquely colorable Cayley graphs

Walter Klotz

Institut für Mathematik, Technische Universität Clausthal
38678 Clausthal-Zellerfeld, Germany

Torsten Sander

Fakultät Informatik, Ostfalia Hochschule für angewandte Wissenschaften
38302 Wolfenbüttel, Germany

Received 24 June 2015, accepted 5 January 2016, published online 15 November 2016

## Abstract

It is shown that the chromatic number $\chi(G) = k$ of a uniquely colorable Cayley graph $G$ over a group $\Gamma$ is a divisor of $|\Gamma| = n$. Each color class in a $k$-coloring of $G$ is a coset of a subgroup of order $n/k$ of $\Gamma$. 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 \to 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 $\chi(G)$ is the smallest number $k$ for which $G$ is $k$-colorable. An optimal coloring of $G$ is a $\chi(G)$-coloring of $G$. The color class of the coloring $f: V \to C$ with respect to color $c \in C$ consists of all vertices $x \in 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

<footnote>E-mail addresses: klotz@math.tu-clausthal.de (Walter Klotz), t.sander@ostfalia.de (Torsten Sander)</footnote>
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 $\delta(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 Lovász [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| \geq (k-1)n - \binom{k}{2}. \qquad (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 = \text{Cay}(\Gamma, S)$ over the finite (multiplicative) group $\Gamma$ with shift set (or symbol) $S \subseteq \Gamma$ has vertex set $V = V(G) = \Gamma$ and edge set

$$E = E(G) = \{\{x, y\} : x, y \in \Gamma, xy^{-1} \in S\}.$$

To avoid loops we demand that the unit element $e \in \Gamma$ is not in $S$. To make $G$ undirected we require that $S$ is self-inverse, $S^{-1} = S$, which means that $s \in S$ always implies $s^{-1} \in 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 $Z_n$ of integers modulo $n$, $Z_n = \{0, 1, \dots, n-1\}$. A well-known circulant graph is the unitary Cayley graph

$$X_n = \text{Cay}(Z_n, U_n) \text{ with } U_n = \{x \in Z_n : \text{gcd}(x, n) = 1\}.$$

Here $\text{gcd}(x, n)$ denotes the greatest common divisor of $x$ and $n$ and $U_n$ is the set of multiplicative units of $Z_n$ considered as a ring. In [15] we proved for $n > 1$ that $\chi(X_n) = p$, where $p$ is a smallest prime divisor of $n$. Bašić and Ilić [2] remarked in passing that $X_n$ 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 $\chi(G) = k$ of a uniquely colorable Cayley graph $G$ over a group $\Gamma$ is a divisor of the number of elements $|\Gamma| = n$ of $\Gamma$. Each color class of $G$ is a coset of some subgroup of order $n/k$ of $\Gamma$. 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| \geq (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 Lovász [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 \in V$ there is an automorphism $\tau$ of $G$ with $\tau(x) = y$. Transitive graphs are regular. We call $G$ weakly transitive if we require the existence of an automorphism $\tau$ of $G$ with $\tau(x) = y$ only for adjacent vertices $x$ and $y$.
**Lemma 2.1.** Let the graph $G = (V, E)$ be weakly transitive und uniquely $k$-colorable. Then $\chi(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 $C_1, C_2$ be an arbitrary pair of color classes of $G$. Since $\chi(G) = k$ there exists a pair $x, y$ of adjacent vertices $x \in C_1$ and $y \in C_2$. As $G$ is weakly transitive we know that there is an automorphism $\tau$ of $G$ with $\tau(x) = y$. Every automorphism of a uniquely colorable graph $G$ maps each color class of $G$ to another color class of $G$. Therefore, $x \in C_1, y \in C_2$ and $\tau(x) = y$ imply $\tau(C_1) = C_2$ and $|C_1| = |C_2|$. 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. $\square$

Let $G = \text{Cay}(\Gamma, S)$ be a Cayley graph. Define the bijection $\tau_a : \Gamma \to \Gamma$ for $a \in \Gamma$ by $\tau_a(x) = xa$. We verify for $x, y \in \Gamma$:

$x, y$ adjacent in $G \Leftrightarrow xy^{-1} \in S \Leftrightarrow (xa)(ya)^{-1} \in S \Leftrightarrow \tau_a(x), \tau_a(y)$ adjacent in $G$.

For $a = x^{-1}y$ we have $\tau_a(x) = y$. This shows that $H(\Gamma) = \{\tau_a : a \in \Gamma\}$ is a subgroup of the automorphism group $\text{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 = \text{Cay}(\Gamma, S)$ the following statements are true.

1. The chromatic number $\chi(G) = k$ divides the number $|V(G)| = |\Gamma| = n$ of vertices of $G$.

2. Every color class $C$ of $G$ is a left coset of a subgroup $U(C) \subseteq \Gamma$ of order $|U(C)| = \frac{n}{k}$.

3. For any two distinct color classes $C_1$ and $C_2$ of $G$ there exists an element $\gamma \in \Gamma$ such that $U(C_2) = \gamma U(C_1) \gamma^{-1}$. If $\Gamma$ 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 = \{a_1, \dots, a_r\}$, $r = n/k$, is a color class of $G$. Define

$$U = U(C) = \{a_i^{-1}a_j : i, j \in \{1, \dots, r\}\}.$$

We prove that $U$ is a subgroup of $\Gamma$.

The unit element $e = a_i^{-1}a_i$ belongs to $U$. For $x = a_i^{-1}a_j \in U$ we have $x^{-1} = a_j^{-1}a_i \in U$. Assume that $x = a_i^{-1}a_j \in U$ and $y = a_s^{-1}a_t \in U$. We are going to show $xy \in U$. The automorphism $\tau_x$ of $G$ maps $a_i$ to $a_j$, $\tau_x(a_i) = a_i x = a_j$. From the unique colorability of $G$ we conclude $\tau_x(C) = C$ and analogously $\tau_y(C) = C$. For arbitrary $\zeta \in C$ we have

$$\begin{align*} \tau_x(\zeta) &= \zeta x = \zeta_1 \in C, \\ \tau_y(\zeta_1) &= \zeta_1 y = \zeta x y = \zeta_2 \in C, \\ xy &= \zeta^{-1}\zeta_2 \in U. \end{align*}$$

Next, we show $C = a_1U$, the left coset of $U$ represented by $a_1$. For every $a_i \in C$ we have $a_i = a_1(a_i^{-1}a_i) \in a_1U$, which implies $C \subseteq a_1U$. Suppose

$$z \in a_1U, z = a_1a_i^{-1}a_j = a_1x, x = a_i^{-1}a_j \text{ for some } i, j \in \{1, \dots, r\}.$$
As above we see $\tau_x(C) = C$. Therefore, $z = a_1x = \tau_x(a_1) \in C$, $C = a_1U$.

3. Let $C_1 = aU_1$ and $C_2 = bU_2$ be different color classes of $G$, $U_1 = U(C_1)$, $U_2 = U(C_2)$. For the automorphism $\tau_d$ of $G$ with $d = a^{-1}b$ we have $\tau_d(a) = b$. The unique colorability of $G$ implies $\tau_d(C_1) = C_2$, hence

$$C_2 = C_1d, bU_2 = aU_1a^{-1}b$$

and therefore

$$U_2 = \zeta U_1 \zeta^{-1} \text{ with } \zeta = b^{-1}a.$$

If $\Gamma$ is abelian, we conclude $U_2 = U_1$. $\square$

<figure><img src="image_1.png" /></figure>

**Corollary 2.3.** If $G = \text{Cay}(Z_n, S)$ is a uniquely colorable circulant graph, then $\chi(G) = k$ is a divisor of $n$. The color classes of $G$ are the residue classes modulo $k$ in $Z_n$. If $S$ is extended by elements $s' \in Z_n$, $s' \neq 0$ modulo $k$, to a self-inverse set $S'$, then $G' = \text{Cay}(Z_n, S')$ is also a uniquely colorable graph with $\chi(G') = k$.

*Proof.* According to Theorem 2.2, the color classes of $G$ are the cosets of a subgroup $U \subseteq Z_n$, $|U| = n/k$. The (additive) cyclic group $Z_n$ has exactly one subgroup of order $n/k$ that is $\langle k \rangle = \{0, k, \dots, (n/k - 1)k\}$, the cyclic subgroup generated by $k$. The cosets of $\langle k \rangle$ are the residue classes modulo $k$ in $Z_n$. The graph $G' = \text{Cay}(Z_n, S')$ is constructed from $G$ by adding edges between different color classes. So the graph remains uniquely colorable with the same chromatic number. $\square$

<figure><img src="image_2.png" /></figure>

**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 = \text{Cay}(\Gamma, S)$ be a uniquely colorable Cayley graph over the abelian group $\Gamma$, $|\Gamma| = n$, $\chi(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 \ge 2$. Moreover, $|E(G)| \ge (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 = \{u_1, \dots, u_r\} \subseteq \Gamma$, $r = n/k$. Without loss of generality let $au_1$ be a vertex of maximum degree $l$ in the subgraph $G_1 = G(C \cup D)$ induced by $C \cup D$ in $G$. The neighbors of $au_1$ in $G_1$ must lie in $bU$. Let these be $bu_{i_1}, \dots, bu_{i_l}$. For $u \in U$ we apply the automorphism $\tau_u$ of $G$ defined by $\tau_u(x) = xu$ to $au_1$ and its neighbors in $G_1$ and conclude:

$$au_1u \in aU \text{ is adjacent to } bu_{i_1}u, \dots, bu_{i_l}u \in bU \text{ for every } u \in U.$$

As $au_1u$ runs through all elements of $aU$ for $u \in U$, we see that all vertices in $aU$ must have the same degree $l$ in $G_1$. The same holds for the vertices of $bU$ since the $r$ vertices of $bU$ have $rl$ edges in $G_1$ and the maximum degree of $G_1$ is $l$.

It is easy to see (cf. Theorem 1 in [11]) that the subgraph $G_1 = G(C \cup D)$ induced by any two color classes $C, D$ of $G$ must be connected. This implies

$$l \frac{n}{k} = |E(G_1)| \ge |V(G_1)| - 1 = 2 \frac{n}{k} - 1$$
so that

$$l \geq 2 - \frac{k}{n} > 1.$$

As $l$ is an integer we have $l \geq 2$. This implies for $|S|$, the degree of regularity of $G$, $|S| \geq 2(k-1)$. Finally, we estimate the number of edges of $G$:

$$|E(G)| = \frac{1}{2} |S| n \geq (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 $\omega(G)$ of a graph $G$ is the largest number of vertices in a complete subgraph of $G$. The clique number $\omega(\bar{G})$ of the complementary graph $\bar{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 $\Gamma$, $|U| = |\Gamma|/k$, $k > 1$ a divisor of $|\Gamma|$. Moreover, let $\{r_1, \dots, r_k\}$ be a system of distinct representatives of the cosets of $U$ in $\Gamma$. Define

$$S = \{r_i - r_j : i, j \in \{1, \dots, k\}, i \neq j\} \text{ and } G = \text{Cay}(\Gamma, S).$$

Then we have:

1. $\chi(G) = \omega(G) = k$.

2. $\chi(\bar{G}) = \omega(\bar{G}) = \frac{|\Gamma|}{k}$.

3. The cosets of $U$ in $\Gamma$ are the color classes of an optimal coloring of $G$.

*Proof.* From the definition of the representatives $r_1, \dots, r_k$ we deduce $S \cap U = \emptyset$. Suppose that $x, y$ belong to the same coset $r_i + U$, $1 \leq i \leq k$. Then we can find elements $u_1, u_2 \in U$ such that $x = r_i + u_1$ and $y = r_i + u_2$. Now $x - y = u_1 - u_2 \in U$ implies $x - y \notin S$, which means that $x$ and $y$ are not adjacent in $G$. The cosets of $U$ partition the vertex set $\Gamma$ of $G$ into $k$ stable sets, i.e. sets of pairwise nonadjacent vertices. So we have

$$\omega(G) \leq \chi(G) \leq k.$$

On the other hand $r_1, \dots, r_k$ induce a clique of size $k$ in $G$. This proves claims 1 and 3.

Let $U = \{u_1, \dots, u_t\}, t = |\Gamma|/k$. The sets

$$K_j = \{r_i + u_j : i = 1, \dots, k\}, \quad 1 \leq j \leq t,$$

induce cliques of size $k$ in $G$, and therefore stable sets of size $k$ in $\bar{G}$. To show that these sets are pairwise disjoint, we assume $x \in K_{j_1} \cap K_{j_2}$ for $j_1 \neq j_2$. We can find $i_1, i_2 \in \{1, \dots, k\}$ such that

$$x = r_{i_1} + u_{j_1} = r_{i_2} + u_{j_2}.$$

Hence,

$$r_{i_1} - r_{i_2} = u_{j_2} - u_{j_1} \in U.$$
From $S \cap U = \emptyset$ we deduce $i_1 = i_2$, which implies $j_1 = j_2$ contrary to our assumption. The sets $K_j$, $1 \le j \le t$, constitute a partition of the vertex set $\Gamma$ of $\overline{G}$ into $t = |\Gamma|/k$ stable sets of $\overline{G}$. Therefore, we have

$$ \omega(\overline{G}) \le \chi(\overline{G}) \le \frac{|\Gamma|}{k}. $$

Finally, claim 2 follows from the fact that every coset of $U$ induces a clique of size $t = |\Gamma|/k$ in $\overline{G}$. $\square$

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, $\Gamma = Z_{12} = \{0, 1, \dots, 11\}$. Let $U = \langle 4 \rangle = \{0, 4, 8\}$ be the cyclic subgroup of $Z_{12}$ generated by 4. Then we have $k = |\Gamma|/|U| = 4$ and $\{r_1, r_2, r_3, r_4\} = \{0, 1, 6, 7\}$ as a system of distinct representatives for the cosets of $U$. We define

$$ S = \{r_i - r_j : i, j \in \{1, \dots, 4\}, i \neq j\} = \{1, 5, 6, 7, 11\} \text{ and } G = \text{Cay}(\Gamma, S). $$

According to Theorem 3.1 the cosets of $U$ in $\Gamma$,

$$ \{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 $Z_{12}$ 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$,

$$ S_{k,n} = \{1, 2, \dots, k-1\} \cup \{n-1, n-2, \dots, n-(k-1)\}, \text{ and } G_{k,n} = \text{Cay}(Z_n, S_{k,n}). $$

Then the circulant graph $G_{k,n}$ is uniquely colorable with

$$ \chi(G_{k,n}) = \omega(G_{k,n}) = k \text{ and } \chi(\overline{G_{k,n}}) = \omega(\overline{G_{k,n}}) = \frac{n}{k}. \quad (3.1) $$

The residue classes modulo $k$ in $Z_n$ are the maximal stable sets of $G_{k,n}$ and the color classes of an optimal coloring of $G_{k,n}$.

*Proof.* The integers $r_1 = 0$, $r_2 = 1, \dots$, $r_k = k-1$ constitute a system of distinct representatives for the cosets of the subgroup $U = \langle k \rangle$ generated by $k$ in $Z_n$. Modulo $n$ we have:

$$ S_{k,n} = \{r_i - r_j : i, j \in \{1, 2, \dots, k\}, i \neq j\}. $$

Now Theorem 3.1 implies (3.1) and the fact that the cosets of $U$, i.e. the residue classes modulo $k$ in $Z_n$, are the color classes of an optimal coloring of $G_{k,n}$. Let $M$ be a stable
set with a maximal number of vertices in $G_{k,n}$. We have $|M| = n/k$ by (3.1). For every $x \in M$ the consecutive integers $x+1, \dots, x+k-1$ (modulo $n$) are adjacent to $x$ and therefore not in $M$. This implies that $M$ is the residue class $x + \langle k \rangle$ in $Z_n$.

Let $F$ be an optimal coloring of $G_{n,k}$, i.e. a coloring of the vertices of $G_{k,n}$ with $k$ colors. Every color class of $F$ must be a maximal stable set of $G_{n,k}$ with $n/k$ elements. We have just shown that these sets are the cosets of $U = \langle k \rangle$ in $Z_n$. Therefore, $G_{k,n}$ is uniquely colorable. $\square$

The graph $G_{k,n} = \text{Cay}(Z_n, S_{k,n})$ is regular of degree $|S_{k,n}| = 2(k-1)$. This implies $|E(G_{k,n})| = (k-1)n$. Hence we immediately obtain:

**Corollary 3.4.** For every divisor $k$ of $n$, $1 < k < n$, the graph $G_{k,n}$ defined in Theorem 3.3 is a uniquely $k$-colorable, circulant graph with $n$ vertices and the minimal number of $|E(G_{k,n})| = (k-1)n$ edges.

**Example 3.5.** Let $X_n = \text{Cay}(Z_n, U_n)$ be the unitary Cayley graph on $n$ vertices, $U_n = \{x \in Z_n : \gcd(x, n) = 1\}$. Suppose that $p$ is the smallest prime divisor of $n$, $1 < p < n$. According to Theorem 3.3 we define

$$S_{p,n} = \{1, 2, \dots, p-1\} \cup \{n-1, n-2, \dots, n-(p-1)\} \text{ and } G_{p,n} = \text{Cay}(Z_n, S_{p,n}).$$

Then $G_{p,n}$ is uniquely colorable and $\chi(G_{p,n}) = \chi(X_n) = p$. The unitary Cayley graph $X_n$ results from $G_{p,n}$ by adding additional edges between different color classes of $G_{p,n}$. So $X_n$ and $G_{p,n}$ are both uniquely colorable with the same color classes.

**Problem 3.6.** Is necessarily $\chi(G) = \omega(G)$ for every circulant uniquely colorable Cayley graph?

# 4 Constructing uniquely colorable graphs by graph products

The direct product $X \times Y$ of graphs $X$ and $Y$ has as its vertex set the cartesian product $V(X) \times V(Y)$. Vertices $(x_1, y_1)$, $(x_2, y_2)$ of $X \times Y$ are adjacent if $x_1$ is adjacent to $x_2$ in $X$ and $y_1$ is adjacent to $y_2$ in $Y$. If $X = \text{Cay}(\Gamma_1, S_1)$ and $Y = \text{Cay}(\Gamma_2, S_2)$ are Cayley graphs, then $X \times Y$ is a Cayley graph $\text{Cay}(\Gamma, S)$ over the direct product $\Gamma = \Gamma_1 \times \Gamma_2$ with shift set $S = S_1 \times S_2$. A product $X \times 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) \to Z_n$ of $X$ induces a proper $n$-coloring $F: V(X) \times V(Y) \to Z_n$ of $X \times Y$ by $F(x, y) = f(x)$ for every $x \in V(X)$, $y \in V(Y)$. As the same is true for $Y$ instead of $X$, we immediately see

$$\chi(X \times Y) \le \min\{\chi(X), \chi(Y)\}.$$

A famous conjecture of Hedetniemi ([12], [17]) states that always equality occurs. We denote by $2K_2$ the graph consisting of two disjoint edges. A graph $X$ is $2K_2$-free if it has no induced subgraph $2K_2$. D. Turzik [18] showed that Hedetniemi's conjecture is true if one of the factors is $2K_2$-free.

**Lemma 4.1.** Let the graph $X$ be $2K_2$-free and let $c: V(X) \times V(Y) \to Z_n$ be a proper $n$-coloring of $X \times Y$. For $y \in V(Y)$ define the map $c_y: V(X) \to Z_n$ by

$$c_y(x) = c(x, y) \text{ for every } x \in V(X).$$

If every $c_y$, $y \in V(Y)$, is an improper coloring of $X$, then $\chi(Y) \le n$.
*Proof.* The map $c_y$ is an improper coloring of $X$ means that there are adjacent vertices $x_1, x_2$ of $X$ such that $c_y(x_1) = c_y(x_2)$. Let $\varphi(y)$ be the least value $c_y(x_1)$ such that there are adjacent vertices $x_1, x_2$ of $X$ with $c_y(x_1) = c_y(x_2)$. We show that $\varphi$ is a proper $n$-coloring of $Y$.

Let $y_1, y_2$ be adjacent vertices of $Y$. Assume $\varphi(y_1) = \varphi(y_2)$. Then we find two pairs $x_1, x_2$ and $x_3, x_4$ of adjacent vertices in $X$ such that

$$c_{y_1}(x_1) = c_{y_1}(x_2) = \varphi(y_1) = \varphi(y_2) = c_{y_2}(x_3) = c_{y_2}(x_4), \\ c(x_1, y_1) = c(x_2, y_1) = c(x_3, y_2) = c(x_4, y_2). \tag{4.1}$$

As $x_1, \dots, x_4$ do not induce a subgraph $2K_2$ in $X$, either $\{x_1, x_2\} \cap \{x_3, x_4\} = D \neq \emptyset$ or $D = \emptyset$ and there is an edge between $\{x_1, x_2\}$ and $\{x_3, x_4\}$. Suppose e.g. $D = \emptyset$ and $x_1, x_3$ are adjacent. Then $(x_1, y_1)$ and $(x_3, y_2)$ are adjacent vertices of $X \times Y$. But now $c(x_1, y_1) = c(x_3, y_2)$ in (4.1) contradicts the fact that $c$ is a proper coloring of $X \times Y$. Similarly, the other cases lead to a contradiction. $\square$

The following theorem extends a result of Greenwell and Lovász [10].

**Theorem 4.2.** Let the graph $X$ be uniquely $n$-colorable and $2K_2$-free. If $Y$ is a connected graph with chromatic number $\chi(Y) > n$, then $X \times Y$ is uniquely $n$-colorable.

*Proof.* We know $\chi(X \times Y) = m \le \chi(X) = n$. Let $c : V(X) \times V(Y) \to Z_m$ be an arbitrary proper $m$-coloring of $X \times Y$. For $y \in Y$ define $c_y : V(X) \to Z_m$ by

$$c_y(x) = c(x, y) \text{ for every } x \in V(X).$$

If $c_y$ is an improper $m$-coloring of $X$ for every $y \in Y$, then Lemma 2.1 implies $\chi(Y) \le m \le n$ contradicting $\chi(Y) > n$. We conclude that there is a vertex $y$ of $Y$ such that $c_y$ is a proper $m$-coloring of $X$. Moreover, $m \le n = \chi(X)$ implies $m = n$. Let $u$ be any neighbor of $y$ in $Y$. Assume that there is a vertex $x_1$ in $X$ such that $c_u(x_1) \neq c_y(x_1)$. As $c_y$ is a proper $n$-coloring of the uniquely $n$-colorable graph $X$, all $n$ colors except $c_y(x_1)$ appear in the range of $c_y$ at the neighbors of $x_1$. In particular, we find a neighbor $x_2$ of $x_1$ with $c_y(x_2) = c_u(x_1)$, $c(x_2, y) = c(x_1, u)$. But this is impossible, because $(x_2, y)$ is adjacent to $(x_1, u)$ in $X \times Y$ and $c$ is a proper coloring of this graph. Therefore, we have

$$c_u(x) = c_y(x) \text{ for every } x \in 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, y_1) = c(x, y_2) \text{ for every } y_1, y_2 \in V(Y) \text{ and every } x \in V(X).$$

This implies that the color classes $C_1, \dots, C_n$ of the arbitrary $n$-coloring $c$ of $X \times Y$ are given by the uniquely determined color classes $D_1, \dots, D_n$ of $X$,

$$C_i = D_i \times Y, \text{ for } i = 1, \dots, n.$$

This means that $X \times Y$ is uniquely $n$-colorable. $\square$

In the following subsections we present some graph candidates for the application of Theorem 4.2.
## 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 $2K_2$-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 $Z_m \times Z_k$.

**Corollary 4.3.** Let $X_i$ be a complete $m_i$-partite graph for $i = 1, \dots, r, r \ge 2$, and $2 \le m_1 \le m_2 \le \dots \le m_r$. Then $X = X_1 \times X_2 \times \dots \times X_r$ has chromatic number $\chi(X) = m_1$. The graph $X$ is uniquely $m_1$-colorable if and only if $m_1 < m_2$.

*Proof.* We have $\chi(X) \le \min\{m_1, \dots, m_r\} = m_1$. If we take one vertex from each color class of $X_i$ we get a clique $Q_i$ of size $m_i$ in $X_i$. Assume that $Q_i$ has vertex set $\{1, 2, \dots, m_i\}$. Then the tuples $(a, a, \dots, a)$ with the $r$-fold entry $a \in \{1, 2, \dots, m_1\}$ define a clique of size $m_1$ in $X$. Thus we see $\chi(X) = m_1$.

If $m_1 < m_2$ we set $Y = X_2 \times \dots \times X_r$. This graph is connected with $\chi(Y) = m_2 > m_1 = \chi(X_1)$. Therefore, we may apply Theorem 4.2 to the product $X_1 \times Y$ and conclude that it is uniquely $m_1$-colorable.

If $m_1 = m_2 = m$, let $f_1$ be an $m$-coloring of $X_1$ and $f_2$ be an $m$-coloring of $X_2$. The colorings of $X$ induced by $f_1$ and by $f_2$ are distinct optimal colorings of $X$. $\square$

## 4.2 Complementary graphs of compass graphs

<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>

The compass graph $CS(k, P)$ is regular of degree 3 and has $n = 6k$ vertices, $k \ge 2$. The vertices $0, 1, \dots, 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 \pm 1 \mod n$. By $P$ we denote a partition of $Z_m = \{0, 1, \dots, m-1\}, m = 2k$, in 2-element subsets which do not
consist of two consecutive integers modulo $m$. For every $\{a, b\} \in P$ we connect the vertices $3a$ and $3b$ by an edge. Figure 1 displays $\text{CS}(3, P)$ with $P = \{\{0, 3\}, \{1, 4\}, \{2, 5\}\}$.

Obviously, every compass graph $\text{CS}(k, P)$ does not contain an induced cycle $C_4$ of length 4. This means for the complementary graph $\overline{\text{CS}}(k, P)$ that it does not contain an induced $2K_2$. The maximal cliques of $\text{CS}(k, P)$ are given by its triangles, which in $\overline{\text{CS}}(k, P)$ define the maximal stable sets. To achieve an optimal coloring of $\overline{\text{CS}}(k, P)$ we must take the sets of vertices $\{x, x-1, x+1 \mod n\}, x \equiv 0 \mod 3$, as color classes. The graph $\overline{\text{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 $A_5$. But we do not know if it is unique.

Infinite sequences of $2K_2$-free, uniquely colorable Cayley graphs can be constructed by the following operations. The $k$-fold join, $\text{join}(k, G)$, of a graph $G$ consists of $k$ disjoint copies $G_1, \dots, G_k$ of $G$. For every $i < j$ every vertex of $G_i$ is connected by an edge to every vertex of $G_j$. Let the $n \times n$-matrix $A$ be an adjacency matrix of $G$ and $J_k$ the $k \times k$-matrix with all entries equal to 1. The Kronecker product $J_k \times A$ is the $(kn) \times (kn)$-matrix which results from $J_k$ by replacing every entry by $A$. The $k$-fold clone, $\text{clone}(k, G)$, is the graph with adjacency matrix $J_k \times A$. We leave the proof of the following statement as an exercise for the reader.

**Proposition 4.4.** If the Cayley graph $G$ is $2K_2$-free and uniquely colorable then $\text{join}(k, G)$ and $\text{clone}(k, G)$ are $2K_2$-free, uniquely colorable Cayley graphs for every integer $k \ge 2$.

## References

[1] S. Akbari, V. S. Mirrokni and B. S. Sadjad, $K_r$-free uniquely colorable graphs with minimum possible edges, *J. Comb. Theory, Ser. B* **82** (2001), 316-318.

[2] M. Bašić and A. Ilić, 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. Bollobás, 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. Lovász, Applications of product coloring, *Math. Acad. Sci. Hungar.* **25** (1974), 335-340.
[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. Klavžar, *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. Lovász, *Stable sets and polynomials*, *Discrete Math.* **124** (1994), 137-153.

[17] C. Tardif, Hedetniemi's conjecture 40 years later, *Graph Th. Notes New York LIV* (2008), 46-57.

[18] D. Turzik, *A note on direct product of graphs*, *Comment. Math. Univ. Carolin.* **24** (1983), 461-463.

[19] S. Xu, *The size of uniquely colorable graphs*, *J. Comb. Theory, Ser. B* **50** (1990), 319-320.