Mixing Circular Colourings

Definitions and mathematical statement

Let $G$ be a finite simple graph. For positive integers $p\ge2q$, a circular $(p,q)$-coloring is a map $f:V(G)\to\{0,\ldots,p-1\}$ satisfying $q\le|f(u)-f(v)|\le p-q$ for every edge. Its reconfiguration graph $\mathcal R_{p,q}(G)$ has all such colorings as vertices; two are adjacent when they differ at exactly one vertex of $G$. Recoloring that vertex may jump to any allowed label, provided the new map is still a valid coloring.

Say that $G$ is $(p,q)$-mixing when this reconfiguration graph is nonempty and connected. Thus any two valid colorings can be linked by a finite sequence of valid single-vertex changes. Define its circular mixing threshold by \[ \mathfrak M_c(G)=\inf\{r\in\mathbb Q:r\ge2,\ G\text{ is }(p,q)\text{-mixing} \text{ for every }p,q\ge1\text{ with }p/q\ge r\}. \] For graphs having an edge this is the source threshold; edgeless graphs are harmless separately under either the palette-one or palette-two convention. The problem asks whether $\mathfrak M_c(G)$ is rational for every finite graph.

The threshold asks for mixing at all sufficiently large ratios, because mixing need not be monotone at particular intermediate ratios. Distinct integer pairs with the same ratio are all included: their palettes and reconfiguration graphs differ. Rationality of the infimum does not assert that mixing holds at the threshold itself. It also does not assert that the threshold is an integer.

Short English statement

Is the eventual threshold for connectivity under single-vertex recoloring of circular graph colorings always a rational number?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3240 (OPG-37907), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Mixing Circular Colourings. Original problem and discussion. http://www.openproblemgarden.org/op/mixing_circular_colourings_0.