Distinguishing Chromatic Number of Random Cayley graphs

Abstract

The \textit{Distinguishing Chromatic Number} of a graph $G$, denoted ${\chi }_D(G)$, was first defined in \cite{collins} as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism $\varphi$ of the graph $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma (A,S)$ defined over certain abelian groups $A$ and show that with probability at least $1-n^{-\Omega (\log n)}$ we have, ${\chi }_D(\Gamma )\le \chi (\Gamma )+1$.

arXiv comment11 pages