1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .