Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph G, denoted χD(G), is defined as the minimum number of colors needed to properly color G such that no non-trivial automorphism of G fixes each color class of G. In this paper, we consider random Cayley graphs Γ defined over certain abelian groups A with |A|=n, and show that with probability at least 1−n−Ω(logn), χD(Γ)≤χ(Γ)+1.