Finite graph colorings without symmetries Let $G$ be a connected finite simple graph with vertex set $V$, $F$ a finite set and let $\Delta(G)$ denote the degree of $G$, i.e. $\Delta(G)= \max_{v\in V} \deg(v)$. We say that a coloring $\phi\colon V \to F$ is asymmetrical if $\text{Iso}(G,\phi) = \{Id_V\}$ , where $\text{Iso}(G,\phi)$ denotes the set of bijections $h\colon V\to V$ preserving both the coloring and the graph structure (note that two adjacent vertices may share the same color). Then let $\Gamma(k)\in \mathbb{N}$ be the infimum of the numbers such that every finite graph $G$ with $\Delta(G) = k$ admits an assymmetrical coloring by $\Gamma(k)$ colors. 
For any $k\in \mathbb{N}$, $\Gamma(k)\leq k^2+2$, to see this consider the graph $G'$ whose set of vertices is the same as that of $G$, and where two vertices $x,x'\in G'$ are adjacent if and only if $d_G(x,x')\leq 2$. This graph admits a proper coloring (any two adjacent vertices have different colors) $\phi$ by $k^2+1$ colors, which we can think of as a coloring on $G$. It is easy to check that the set $\text{Iso}(G,\phi)$ acts freely on $G$. Define now $\tilde{\phi}$ by choosing an arbitrary point $x_0\in V$ and mapping it to a color different from those in $\phi$. Then $\text{Iso}(G,\tilde{\phi})$ acts freely on $G$ and must map $x_0$ to $x_0$.
However, this bound seems too large. For example, for $k=2$, it seems that $\Gamma(2)=3$.
Question: Has the function $\Gamma$ been studied? If so, what values of $\Gamma(k)$ are known? Is there a better bound for $\Gamma(k)$ than $k^2+2$?
 A: In http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r18
Albertson and Collins refer to this parameter as the distinguishing number of the graph, and there is a reasonably large literature on the topic. However, if my recollection is correct, the valency of the graph does not play much of a role
in this work.
A: I think $k+1$ always suffice. Here is an algorithm that produces such a coloring. 
Suppose the set of colors is $\{0,\ldots,k\}$. First, pick a vertex, say $v$, and color it $0$. We will never use that color again. Now, repeat the following procedure, iteratively: choose a vertex $u$ which is colored but has at least one uncolored neighbour, and color the uncolored neighbours of $u$, in such a way that all neighbours of $u$ have different colors (using only the colors from $\{1,\ldots,k\}$). This is clearly possible, since we have $k$ colors available, and $u$ has at most $k$ neighbours. Keep doing this until everything is colored. (Since the graph is finite and connected, this will eventually happen.)
Now, $v$ is clearly fixed by any color-preserving automorphism, since it is the unique vertex of that color. Moreover, any neighbour of a fixed vertex is clearly also fixed, since it is the unique neighbour of that vertex with that color. By induction (and connectedness), a color-preserving automorphism must fix every vertex.
As I commented earlier, this is sharp, as can be seen with the complete and complete bipartite graph. There are also other "sharp" graphs, such as the cycle of order $5$. I wonder if it might be possible to classify them.
