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$?