Polynomial mixing-time conjecture for Glauber dynamics on graph colourings

From papers

Let GG be a graph with maximum degree 4Δ44\Delta4, and let kk be an integer satisfying

kΔ+2.k \geq \Delta+2.

Consider the Glauber dynamics on the set of kk-colourings of GG, in which a uniformly random vertex is recoloured with a uniformly random available colour.

Polynomial mixing-time conjecture. For any graph GG, the Glauber dynamics on the kk-colourings of GG for kΔ+2k\geq\Delta+2 has polynomial mixing time.

This conjecture asserts rapid mixing at the standard threshold of two more colours than the maximum degree. Polynomial mixing is important because it would make Glauber dynamics an efficient sampler for uniformly random proper colourings; the source presents this as a well-known conjecture and does not state a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Marc Heinrich, “Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth”, arXiv:2010.16158 (2020).

Solutions 0

No solutions have been posted yet.