Vertex transitive graphs G with chisub D(G) greater then chi(G) and small automorphism group - Balachandran, Niranjan (Ars mathematica contemporanea, 2019)
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 \in \{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 \in \mathbb{N} $?, there exists an infinite sequence of vertex-transitive graphs ?$G_i = (V_i, E_i)$? such that (1.) ?$χ_D (G_i) > χ (G_i) > k$?, and (2.) ?$|\rm{Aut}(G_i)| < 2k|V_i|$?, where ?$\rm{Aut}(G_i)$? denotes the full automorphism group of ?$G_i$?. In particular, this answers a question posed by the first and second authors of this paper.
Keywords: Cayley graphs; Cayleyjevi grafi; distinguishing chromatic number; razločevalno kromatčno število; vertex transitive graphs; vozliščno tranzitivni grafi