Distinguishing Chromatic Number of Random Cayley graphs
| Autor: | Balachandran, Niranjan, Padinhatteeri, Sajith |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\phi$ 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$. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|