Distinguishing threshold of graphs

A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing threshold of $G$, denoted by $theta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $theta(G)$, find its relation to the cycle structure of the automorphism group of $G$ and prove that $theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K_n}$. Finally, we consider the graphs in the Johnson scheme for their distinguishing numbers and thresholds.