I talked briefly about how to get from one 3-coloring of a grid graph to another by changing one vertex color at a time, in a recent blog post about analogous problems for origami folding patterns. It turns out that this problem of reconfiguring 3-colorings has been treated in much greater generality in the 2007 doctoral dissertation of Luis Cereceda, “Mixing graph colourings”, as I discovered when I read the dissertation in the process of writing a new Wikipedia article on Cereceda’s conjecture, the conjecture that the space of \((d+2)\)-colorings of \(d\)-degenerate graphs (under moves that change the color of one vertex at a time) has at most quadratic diameter. Here’s an illustration from the new article showing the space of 3-colorings of a path graph:

The space of 3-colorings of a path graph

Cereceda proved that the following properties of a graph are equivalent:

  • It has a connected space of 3-colorings.
  • Every 3-coloring has a height function.
  • It is bipartite and is not “pinchable” to a 6-cycle

If we consider the three colors to be used for 3-colorings to be the numbers 0, 1, and 2 (mod 3) then a height function can be defined as an assignment of integers (not mod 3) to the vertices, such that taking them mod 3 produces the given coloring, and such that adjacent vertices have heights that differ by \(\pm 1\). If it exists for a given coloring, it can be constructed easily by choosing the height of one vertex arbitrarily and then using the \(\pm 1\) requirement for adjacent heights to propagate this choice to neighbors in the graph until every vertex has a height. What can go wrong is that this propagation somehow leaves two adjacent vertices with heights that are too far apart. For instance, if the colors around a 6-cycle have the cyclic order 0–1–2–0–1–2 then you will come back to the start six units higher than you started.

Continuing to explain the terms in Cereceda’s equivalence, I think the 6-cycle pinchability condition is most easily explained in terms of graph homomorphisms, maps from one graph to another that preserve adjacency. Consider a 6-cycle, 3-colored 0–1–2–0–1–2. It is also a bipartite graph, 2-colored black–white–black–white–black–white, with one vertex for each combination of colors in the 3-coloring and the 2-coloring. If you have any 3-coloring of a bipartite graph, you can map it onto the 6-cycle so that both the 3-coloring and the bipartition are preserved. If your 3-coloring does not have a height function (that is, there is a cycle that, when you propagate heights around it, comes back to its start at a different height) then the winding number of this cycle, as it maps around the 6-cycle, will tell you the difference in heights from start to end (divided by six). So a coloring without a height function gives you a homomorphism to the 6-cycle in which some cycle has nonzero winding number. On the other hand, if you have such a homomorphism, you can lift the colors from the 6-cycle back to the starting graph to give you a coloring without a height function. Cereceda’s “pinching” operations are a special type of homomorphism in which vertices at distance two from each other are repeatedly merged. Not every homomorphism comes from pinching in this way (with pinches you can only map a 12-cycle once around a 6-cycle, not twice around, for instance) so the proof that pinching homomorphisms exist for graphs without height functions is a little more complicated.

It’s possible to construct in polynomial time the shortest sequence of color changes to go from one 3-coloring to another, whenever the space of colorings is connected. Cereceda almost finds this algorithm but misses a small trick and ends up stating its existence only as a conjecture. As I explained in my previous post, if you choose the correct offset for the height functions of the two colorings, you can find this shortest sequence by greedily changing the color at a vertex of one color where the current height is farthest from the goal height. The trick that Cereceda misses is that if you don’t know the correct offset between the two height functions, you can just try them all (or more quickly use a median algorithm to find the optimal offset and the distance between colorings in linear time).

Unfortunately, as Cereceda proved, testing pinchability to a 6-cycle is \(\mathsf{NP}\)-complete and therefore testing the connectivity of the space of 3-colorings (and the applicability of the height-based shortest reconfiguration algorithm) is \(\mathsf{coNP}\)-complete. For instance, I’m pretty sure the 10-vertex Möbius ladder shown below has height functions for all its 3-colorings, but I don’t know of an elegant way to prove this, and \(\mathsf{coNP}\)-completeness suggests that not all graphs have elegant proofs for this. This graph has lots of 6-cycles, for instance formed by any diagonal and the path around the outer cycle connecting its two endpoints. But trying to map the whole graph to a 6-cycle by folding it flat across a diagonal doesn’t work because it would map some edges to non-edges, and nothing else seems to work either.

A 10-vertex Möbius ladder

To save this post from being content-free, I want to describe a more easily recognized family of graphs that meets Cereceda’s criterion, and does have height functions for all its 3-colorings (so we can quickly find the shortest reconfiguration sequences in these graphs). It is the class of graphs in which the cycle space is generated by the 4-cycles, or in other words the graphs in which there exists a cycle basis consisting only of 4-cycles. These graphs can be recognized simply by doing some mod-2 linear algebra to test whether the space generated by the 4-cycles has the same dimension as the cycle space. For instance, the Möbius ladder above is not in this class because the dimension of its cycle space (the number of edges beyond the ones in a spanning forest) is six but its number of 4-cycles (the cycles between two consecutive diagonals) is only five. Despite this example, the graphs generated by 4-cycles include a lot of natural classes of graphs that we might want to reconfigure 3-colorings of:

To prove that Cartesian products preserve the property of being generated by 4-cycles, consider any cycle \(C\) in the product graph; we want to represent it as a mod-2 sum of 4-cycles. If two consecutive edges of \(C\) come from the two different factors, then the product of these edges is a 4-cycle, and adding this 4-cycle to \(C\) swaps the order of the two edges within \(C\). By repeated swaps we can segregate all the edges from the two factors from each other, changing \(C\) into two cycles, one from each factor, that meet at a common vertex. Then we can represent the two cycles separately within the two factors.

It’s straightforward to see that when 4-cycles generate the \(\mathbb{Z}\)-homology of a graph, then height functions always exist, because the height difference around any cycle is the sum of the height differences of the 4-cycles generating it, which are all zero. But here by using the binary cycle space we’re looking at the \(\mathbb{Z}_2\)-homology, which might be a different thing. There could be graphs whose \(\mathbb{Z}_2\)-homology is generated by 4-cycles but whose \(\mathbb{Z}\)-homology isn’t. For instance I think that adding one bipartite edge to the 10-vertex Möbius ladder produces an example of this phenomenon. So we need a proof that \(\mathbb{Z}_2\)-homology is good enough. Or in simpler terms, when the cycle space is generated by 4-cycles, all 3-colorings have height functions.

We’ll prove this by contradiction, so let’s suppose that we have the smallest possible counterexample. That is, we have a graph \(G\), a 3-coloring of \(G\), and a cycle \(C\) in \(G\), such that the cycle space of \(G\) is generated by 4-cycles but going around \(C\) using the \(\pm 1\) rule to propagate heights produces a different height than you started with. By “smallest” I mean first, that \(C\) is as short as possible, second, that for that length of \(C\) the rest of \(G\) has as few vertices as possible, and third, that the number of 4-cycles in the representation of \(C\) is as small as possible.

Then \(C\) cannot have any chords, because if it did then a chord plus one of the two segments of \(C\) connecting the chord endpoints would form a shorter cycle with the same inconsistent heights. Because we are assuming that \(G\) is generated by 4-cycles, consider any set \(S\) of 4-cycles whose sum is \(C\). That is, each edge of \(C\) appears an odd number of times in cycles of \(S\), and each other edge of \(G\) appears an even number of times (possibly zero). Each 4-cycle in \(S\) must have a coloring of the form \(x\)–\(y\)–\(x\)–\(y\) or \(x\)–\(y\)–\(z\)–\(y\) for some colors \(x\), \(y\), and \(z\). If at least one of the two \(y\)-colored vertices does not belong to \(C\), form a smaller graph \(G\) by merging these two \(y\)-colored vertices. This merger does not change \(C\) or the coloring, so \(C\) stays a bad cycle. And it doesn’t change the property of \(G\) that it is generated by 4-cycles, because any cycle in the merged graph can be lifted to a cycle in the unmerged graph (possibly passing through \(y\)–\(x\)–\(y\) in the merged 4-cycle and possibly not simple), represented by 4-cycles in \(G\) itself, and then merged back down to get a representation in the smaller graph. But because we’re assuming \(G\) was the smallest possible counterexample, this shrinkage can’t happen, so all of the 4-cycles in \(S\) have both \(y\)-vertices in \(C\).

Now if we have a 4-cycle with two \(y\)-vertices in \(C\), at least one of the other two vertices does not belong to \(C\), because \(C\) must be longer than four edges (else it would not have a bad coloring) and we’ve already ruled out the possibility that \(C\) has the chords that would be needed to make a 4-cycle using vertices only from \(C\). Let \(v\) be this vertex outside of \(C\), so we have a path \(y\)–\(v\)–\(y\) connecting the two \(y\)-vertices in \(C\). One of two things can happen: First, the two \(y\)-vertices might only be two units apart in \(C\). But then, replacing the two-edge path between them by the path through \(v\) produces a new bad cycle of the same length, in the same graph \(G\), representable by a smaller set of 4-cycles. This contradicts our choice of \(C\) and \(G\) as being the smallest possible counterexample. Second, when the two \(y\)-vertices are farther apart in \(C\), there are two cycles formed by path \(y\)–\(v\)–\(y\) and by one of the two paths in \(C\) connecting the same two \(y\)-vertices. Both of these cycles are shorter than \(C\), and at least one of them continues to have a bad coloring. So again we have found a smaller counterexample and a contradiction.

This case analysis leading in all cases to a contradiction shows that a smallest counterexample cannot exist, and therefore that all graphs generated by 4-cycles have height functions for all of their 3-colorings.

(Discuss on Mastodon; see also an earlier post on reconfiguring 3-colorings of cycles using stronger moves; edited 2019-11-27 to correct rectraction vs pinchability in Cereceda’s characterization)