Can every coloring of a graph be obtained by recoloring Kempe chains?

Given a graph $G(V, E)$ and a proper vertex coloring $c:V\rightarrow X$ such that there are at least two distinct colors $a,b\in c(V)$, a $(a,b)$-Kempe chain is a connected component from the subgraph of $G$ induced by the vertices whose are colored either $a$ or $b$.

An interesting property of a $(a,b)$-Kempe chain is the fact that the coloring $c′:V\rightarrow X$ given by

• $c′(v):=c(v)$ if $v$ is not contained in the chain;
• $c′(v):=a$ if $v$ is contained in the chain and $c(v)=b$;
• $c′(v):=b$ if $v$ is contained in the chain and $c(v)=a$;

is also a proper coloring. Let's call the coloring $c′$ of Kempe recoloring of $c$. Notice that a coloring can have several Kempe recolorings.

I would like to know if, fixed two proper vertex colorings $c_0$, $c$ of $G$, there is a sequence of colorings $c_1,c_2,\cdots,c_n$ such that $c_n=c$ and $c_i$ is a Kempe recoloring of $c_{i−1}$, $i\in\{1, 2, \cdots, n\}$.

I have no reason to believe that this statement is true. However, I could not find any counter example. It is immediate to see that the statement is true if $G$ is $2$-colorable, so maybe an induction argument could apply. It's also easy to see that the statement is true if $c$ can be obtained from $c_0$ by a permutation of the colors.

Solution 1:

No, this is not true. Let $G$ be the triangular prism, and consider any $3$-colouring, say:

Then the edge set of $G$ is the disjoint union of three connected Kempe chains (indicated in different dash patterns), each of which collects all vertices of colour $a$ or $b$ in a single component. Hence the only Kempe recolourings are permutations of the colours. In particular, it is not possible to cyclically rotate the colours of the outer triangle while leaving the inner triangle as it is. (One such rotation leaves a proper colouring; the other one does not.)

Added later: I recently stumbled upon literature on this question. The above example (which I found by computer search) had been known before. Several authors of recent papers attribute this example to J. van den Heuvel [vdH13], but it seems plausible that it had been known before that. More recently, Feghali, Johnson, and Paulusma [FJP17] and Bonamy, Bousquet, Feghali and Johnson [BBFJ19] proved that the triangular prism is exceptional:

Theorem A. Let $k \geq \Delta \geq 3$. If $G$ is a connected graph with maximum degree $\Delta$, then all $k$-colourings of $G$ are Kempe-equivalent, unless $G$ is the triangular prism.

The proof is divided over several papers. If $G$ is $(k-1)$-degenerate (meaning that every induced subgraph of $G$ has minimum degree at most $k - 1$), then the result follows from Proposition 2.1 in [VM81] (the authors claim that this result was already implicit in [Mey78]). Otherwise, $G$ must be $k$-regular, in which case the result is proved in [FJP17] (for $k = 3$) and [BBFJ19] (for $k \geq 4$).

A closely related result is Brooks' theorem, which states that every connected graph $G$ of maximum degree $\Delta$ has a proper vertex colouring with $\Delta$ colours, unless $G$ is a complete graph or an odd cycle. These two results can be paraphrased as stating that there are many $k$-colourings if $k \geq \Delta \geq 3$ and that they are all Kempe equivalent (except if $G$ is complete or the $3$-prism).

This is still an active area of research. For instance, two weeks ago, a paper [BDL21] was submitted to arXiv where the authors try to obtain upper bounds for the number of Kempe recolourings needed in Theorem A, and last week a list-colouring version of Theorem A was announced on arXiv [CM21]. (Disclaimer: I don't have the expertise to judge the novelty and/or correctness of these results, but it looks legitimate.)

References.

[Mey78]: H. Meyniel, Les 5-colorations d'un graphe planaire forment une classe de commutation unique, Journal of Combinatorial Theory, Series B, volume 24, issue 3, pp. 251–257, 1978. https://doi.org/10.1016/0095-8956(78)90042-4 (open access).

[VM81]: M. Las Vergnas and H. Meyniel, Kempe classes and the Hadwiger Conjecture, Journal of Combinatorial Theory, Series B, volume 31, issue 1, pp. 95–104, 1981. https://doi.org/10.1016/S0095-8956(81)80014-7 (open access).

[vdH13]: J. van den Heuvel, The complexity of change. In: Surveys in Combinatorics, London Mathematical Society Lecture Notes Series, volume 409, Cambridge University Press, 2013, pp.127–160. https://doi.org/10.1017/CBO9781139506748.005 (currently behind a paywall).

[FJP17]: C. Feghali, M. Johnson, and D. Paulusma, Kempe equivalence of colourings of cubic graphs, European journal of combinatorics, volume 59, pp. 1–10, 2017. https://doi.org/10.1016/j.ejc.2016.06.008 (open access).

[BBFJ19]: M. Bonamy, N. Bousquet, C. Feghali, and M. Johnson, On a conjecture of Mohar concerning Kempe equivalence of regular graphs, Journal of Combinatorial Theory, Series B, volume 135, pp. 179–199, 2019. https://doi.org/10.1016/j.jctb.2018.08.002 (currently behind a paywall).

[BDL21]: M. Bonamy, V. Delecroix, and C. Legrand–Duchesne, Kempe changes in degenerate graphs, arXiv preprints, 2021. https://arxiv.org/abs/2112.02313

[CM21]: D.W. Cranston and R. Mahmoud, Kempe euivalent list colorings, arXiv preprints, 2021. https://arxiv.org/abs/2112.07439