ChapterZero

Here’s an interesting, and at first glance research caliber, problem I came across in the process of doing one of my problem sets:

Let be a planar graph, and an integer. Then the set of ‘feasible -coloring’ of such that , i.e. the set of all possible assigment of distinct colors to the vertices of the graph so that neighbors have different colors, is non-empty (this is the content of the famous Four Color Theorem).

Here’s the question. We can consider this set to be the set of vertices for a new graph in which two colorings are neighbors iff they differ on exactly one vertex. When is this graph connected? I.e. when can I change an arbitrary feasible coloring into another one by sequentially changing the color of single vertices in such a way that at each step the resulting coloring remains feasible?

This problem came up because one of the assigned problems is to design a Metropolis algorithm that uniformly samples from the set of possible -colorings on a graph. In order for the associated Markov chain to be irreducible, we need the set of feasible colorings to be connected in the above sense. But this is not always the case. Take the set of 4-colorings of a fully connected 4 vertex graph– there are exactly 4 colorings, and not enough ‘wiggle’ room to move from one to the other.

On a related note, I recommend MatGraph for anyone using Matlab who wants to mess around with and visualize graphs. I spent so much time looking for an example of a large graph and a feasible 4-coloring on the Internet (for some reason people have posted ‘test’ graphs that are good for testing coloring algorithms, but without any colorings), before I realized that Matgraph can color graphs for you, and display them too.

Possibly relevant posts:

• More connectedness of colorings (2/21/2007)
• Coloring Problem (12/21/2004)
• Practical Graph Theory (2/18/2003)