# How to show the state space of proper vertex-coloring is connected?

Given a graph $$G$$, we can view each proper vertex-coloring of $$G$$, i.e., two adjacent vertices of $$G$$ receive different colors, as a state. And two states are adjacent if the two colorings only differ at one vertex.

If it is allowed to use at most $$2\Delta+1$$ colors for the proper coloring, where $$\Delta$$ is the maximum degree of $$G$$. I am wondering how to prove the state space is connected? I.e., given any two proper coloings of $$G$$, each time we are allowed to modify the color of one vertex to get a proper coloring, so that we can go from one proper coloring to the other?

If $$2\Delta+1$$ is not enough, what's about $$3\Delta+1$$?

$$\Delta+2$$ colors is always enough, as originally proved by Mark Jerrum here. The idea is that one can move from any one coloring $$f$$ to another $$g$$ by considering vertices one by one in any order: when considering vertex $$v$$, we want to change its color from $$f(v)$$ (or whatever it currently has) to $$g(v)$$. Its earlier neighbors are already colored by $$g$$ so that's ok, while each later neighbor $$x$$ of $$v$$ can be recolored to some color that is neither $$f(v)$$ nor $$g(v)$$ nor whatever other neighbors of $$x$$ currently have (this exludes at most $$1+1+\Delta-1$$ colors).

$$\Delta+1$$ is not enough as $$n$$-colorings of a complete graph on $$n$$ vertices show ($$\Delta=n-1$$).

See also Cereceda's thesis, Proposition 2.6 and Theorem 2.7, which shows that actually it suffices to used $$\mathrm{deg}(G)+2$$ colors, where $$\mathrm{deg}(G)$$ is the degeneracy of $$G$$.

In case you're wondering: $$\chi(G)+2$$, or in fact any function of $$\chi(G)$$, won't work. As a counterexample consider the complete bipartite graph $$K_{n,n}$$ with colors $$1,\dots,n$$ on each side – then $$\chi=2$$, but no color can change if you allow only $$\leq n$$ colors). Cereceda's thesis has a lot more examples, like planar graphs.

Jerrum's paper shows that with $$\geq 2\Delta+1$$ colors doing recoloring randomly will reach all colorings fairly quickly, giving an efficient algorithm to estimate the number of colorings, for example.

$$2(\Delta+1)$$ is enough. I have to think if it is also necessary, my intuitive guess is it is not.

Every graph can be colored using a greedy algorithm (picks legal colors to vertices iteratively) using $$\Delta + 1$$ colors.

Denote the colors by $$[2(\Delta + 1)]:=\{1,2,...,2(\Delta + 1)\}$$.
Denote a proper coloring of $$G$$ using the first $$\Delta + 1$$ colors by $$c_1$$, and a proper coloring using the last $$\Delta + 1$$ by $$c_2$$.

Prop: Those two coloring are connected.

Proving connectedness

It can be done by induction.
Let $$G$$ be colored by some coloring $$c$$, I'll show how to get to some other coloring $$c'$$.

The step is, pick some vertex $$v\in V(G)$$ if you can color $$v$$ in $$c'(v)$$ then we are done (By induction hypothesis).

Otherwise (you can't color $$v$$ in $$c'$$), color the entire graph using all the colors that are not being used by $$c$$. (There are $$\Delta + 1$$ colors, so it can be done)

We know $$c'(v)$$ appeared in the previous coloring, so it does not appear in the new one, therefore we can color $$v$$ in $$c'(v)$$ and we are done by I.H

On second thought, I think the coloring space is connected if you allow $$\chi(G) + 1$$, where $$\chi(G)$$ is the minimal number of colors needed to properly color $$G$$.

Basically using the argument, but I'll have to think about it.