Distinguishing Chromatic Number of Random Cayley graphs

The \textit{Distinguishing Chromatic Number} of a graph $G$, denoted $χ_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 $ϕ$ of the graph $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $Γ(A,S)$ defined over certain abelian groups $A$ and show that with probability at least $1-n^{-Ω(\log n)}$ we have, $χ_D(Γ)\leχ(Γ) + 1$.

No reviews yet.

No comments yet.