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

Niranjan Balachandran, Sajith Padinhatteeri, Pablo Spiga


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 ∈ ℕ, 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.


Distinguishing chromatic number, vertex transitive graphs, Cayley graphs

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications