  For a graph $G$, a $k$-coloring $c:V(G)\to \{1,2,\ldots, k\}$ is called
distinguishing, if the only automorphism $f$ of $G$ with the property
$c(v)=c(f(v))$ for every vertex $v\in G$ (color-preserving automorphism), is
the identity. In this paper, we show that the number of distinguishing
$k$-colorings of $G$ is a monic polynomial in $k$, calling it the
distinguishing polynomial of $G$. Furthermore, we compute the distinguishing
polynomials of cycles and complete multipartite graphs. We also show that the
multiplicity of zero as a root of the distinguishing polynomial of $G$ is at
least the number of orbits of $G$.
