Vertex transitive graphs G with χD(G) > χ(G) and small automorphism group

For a graph G and a positive integer k, a vertex labelling f : V (G) → {1, 2, . . ., k} is said to be k-distinguishing if no non-trivial automorphism of G preserves the sets f− 1(i) for each i ∈ {1, . . ., k}. The distinguishing chromatic number of a graph G, denoted χD(G), is defined as the minimum k such that there is a k-distinguishing labelling of V (G) which is also a proper coloring of the vertices of G. In this paper, we prove the following theorem: Given k ∈ N, there exists an infinite sequence of vertex-transitive graphs Gi = (Vi, Ei) such that 1. χD(Gi) > χ(Gi) > k, 2. |Aut(Gi)| < 2k|Vi|, where Aut(Gi) denotes the full automorphism group of Gi. In particular, this answers a question posed by the first and second authors of this paper.