Reconfiguring 3-colorings
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
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
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
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:
- Trees
- Rectangular grid graphs and higher-dimensional hyperrectangular grid graphs
- Squaregraphs
- The dual graphs of simple line arrangements
- Complete bipartite graphs
- Chordal bipartite graphs
- The Cartesian products of other graphs generated by 4-cycles
To prove that Cartesian products preserve the property of being generated by 4-cycles, consider any cycle
It’s straightforward to see that when 4-cycles generate the
We’ll prove this by contradiction, so let’s suppose that we have the smallest possible counterexample. That is, we have a graph
Then
Now if we have a 4-cycle with two
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)