Sampling Line-Graph Colorings with Constant Extra Colors

Abstract

Let $G$ be the line graph of a finite simple graph, with $n\ge 1$ vertices and maximum degree $\Delta$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_{\Delta }(n\log (n/\epsilon ))$ steps for every integer $q\ge \Delta +5$. Our proof uses the Bochner framework of Chen and Liu (2026).

arXiv comment10 pages, 1 figure