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

Question

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

Answer 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.

Answer 2

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