Importance: Low ✭
 Author(s):
 Subject:
 Keywords:
 Recomm. for undergrads: yes
 Posted by: Jon Noel on: September 22nd, 2012
Question   Is always rational?

Given a proper -colouring of a graph , consider the following 'mixing process:'

\item choose a vertex ; \item change the colour of (if possible) to yield a different -colouring of .

A natural problem arises: Can every -colouring of be generated from by repeatedly applying this process? If so, we say that is -mixing.

The problem of determining if a graph is -mixing and several related problems have been studied in a series of recent papers [1,2,4-6]. The authors of [4] provide examples which show that a graph can be -mixing but not -mixing for integers . For example, given consider the bipartite graph which is obtained by deleting a perfect matching from . It is an easy exercise to show that for is -mixing if and only if and . This example motivates the following definition.

Definition   Define the mixing threshold of to be

An analogous definition can be made for circular colouring. Recall, a -colouring of a graph is a mapping such that if , then . As with ordinary colourings, we say that a graph is -mixing if all -colourings of can be generated from a single -colouring by recolouring one vertex at a time.

Definition   Define the circular mixing threshold of to be

Several bounds on the circular mixing threshold are obtained in [3], including the following which relates the circular mixing threshold to the mixing threshold.

Theorem  (Brewster and Noel ] For every graph ,

As a corollary, we have the following: if , then . However, examples in [3] show that the ratio can be arbitrarily large in general.

Regarding the problem of determining if is rational, it is worth mentioning that there are no known examples of graphs for which is not an integer.

Other problems are also given in [3]. One can check that and . However, the only graphs which are known to satisfy are in some sense related to , eg. trees and complete bipartite graphs.

Question   Is there a non-bipartite graph such that ?

Using an example from [4], it is shown in [3] that if is an integer, then there is a graph such that if and only if . A natural question to ask is whether a similar result holds for the circular chromatic number. Again, certain bipartite graphs are an exception.

Question   Is there a non-bipartite graph such that ?

Also, the example of shows that the circular mixing threshold is, in general, not attained. However, the following problem is open.

Question   Is the circular mixing threshold always attained for non-bipartite graphs?

For more precise versions of the last three questions, see [3].

## Bibliography

[1] P. Bonsma and L. Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoret. Comput. Sci. 410 (2009), (50): 5215--5226.

[2] P. Bonsma, L. Cereceda, J. van den Heuvel, and M. Johnson. Finding paths between graph colourings: Computational complexity and possible distances. Electronic Notes in Discrete Mathematics 29 (2007): 463--469.

*[3] R. C. Brewster and J. A. Noel. Mixing Homomorphisms and Extending Circular Colourings. Submitted. pdf.

[4] L. Cereceda, J. van den Heuvel, and M. Johnson. Connectedness of the graph of vertex-colourings. Discrete Math. 308 (2008), (5-6): 913--919.

[5] L. Cereceda, J. van den Heuvel, and M. Johnson. Mixing 3-colourings in bipartite graphs. European J. Combin. 30 (2009), (7): 1593--1606.

[6] L. Cereceda, J. van den Heuvel, and M. Johnson. Finding paths between 3-colorings. Journal of Graph Theory, 67 (2011), (1): 69--82.

[7] J. A. Noel. "Jonathan Noel - Mixing Circular Colourings." Webpage.

* indicates original appearance(s) of problem.