Glauber (Δ+1)-colouring mixing without Δ = o(n)
Informal: Δ = o(n) condition not necessary for Corollary 2 · arXiv:1811.12650
Status open high confidence
The informal remark that the condition $\Delta = o(n)$ in Corollary 2 is probably not necessary has not been addressed in the literature found. The broader area of Glauber dynamics for graph colourings has seen major advances (spectral independence, high-dimensional expansion) since 2018, but these developments focus on the regime $k \geq \Delta+2$ or $k \geq (11/6)\Delta$ and do not directly address the almost-uniform sampling question for exactly $\Delta+1$ colours under weaker degree assumptions. No follow-up paper specifically resolving or refuting this informal conjecture was found.
Reviewer notes. This is an informal remark (not a numbered conjecture) appearing immediately after Corollary 2 in arXiv:1811.12650. The authors suggest the $\Delta = o(n)$ hypothesis is likely an artifact of the proof technique used to show that a uniformly random $( \Delta+1)$-colouring is almost certainly not frozen, enabling Glauber dynamics to serve as an almost-uniform sampler. The $\Delta+1$ colouring regime is known to behave very differently from $k \geq \Delta+2$ (mixing time can be exponential in the worst case), which may explain why this specific remark has not attracted dedicated follow-up. No follow-up found in the indexed literature.
Context
Corollary 2 states that for a graph on $n$ vertices with $\Delta = o(n)$, Glauber dynamics for $(\Delta+1)$-colourings starting at a uniformly random colouring gives an almost uniform sampler. The authors remark immediately after the corollary that the constraint $\Delta = o(n)$ is likely an artifact of the proof technique.
Notes. Stated in running prose immediately after Corollary 2: 'The condition Δ = o(n) is probably not necessary.' PDF source.
Source paper
Frozen $(Δ+1)$-colourings of bounded degree graphs
Marthe Bonamy, Nicolas Bousquet, Guillem Perarnau · 2018-11-30
https://arxiv.org/abs/1811.12650
PDF source