Proper Distinguishing Colorings with Few Colors for Graphs with Girth at Least 5

Abstract

The distinguishing chromatic number, ${\chi }_D(G)$, of a graph $G$ is the smallest number of colors in a proper coloring, $\phi$, of $G$, such that the only automorphism of $G$ that preserves all colors of $\phi$ is the identity map. Collins and Trenk conjectured that if $G$ is connected with girth at least 5 and $G\ne C_6$, then ${\chi }_D(G)\le \Delta +1$. We prove this conjecture.

arXiv comment9 pages, 3 figures; expanded introduction and bibliography from version 1