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

• My guess is that $\Gamma(k)=k+1$, which is achieved by both the complete and complete bipartite graph. I think this may even be within reach, I'll try to think about it. Apr 13 '16 at 20:20

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.

• In fact, from what I remember about talks on this subject, I think it might be a reasonable conjecture that, for every $k$, there are only finitely many graphs that have distinguishing number greater than $2$. Apr 13 '16 at 23:26
• Thank you very much for your kind help. In fact your approach is very similar to what I wrote in the second paragraph, I don't know why I thought that one needed to have vertices have different colors if their distance was <= 2 when, as you have proved, one only needs a proper coloring with a distinguished vertex. What you say in the comment that one only needs 2 colors for almost every graph seems very interesting, do you know where I could find more information? Again, thank you for your time. Apr 13 '16 at 23:50
• First, I'd like to emphasise that the colouring above is not necessarily proper (adjacent vertices may have the same color), but that is what you asked for. (In fact, if you insist on a proper coloring, then the complete bipartite graphs shows that you need at least $2k$ colors.) As for needing only $2$ colors for most graphs, I'm far from an expert on this, but if you search for papers about "distinguishing number", you'll find that more than half of them deal with exactly this question: showing that, in many families of graphs, all but very few have distinguishing number $2$. Apr 14 '16 at 0:12

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.

• Thank you very much for your answer, I did not know that it was referred to as the distinguishing number. Unfortunately I was interested in particular in some kind of relation between the valency and this parameter. Apr 13 '16 at 23:13