PreprintarXiv licencearXiv
Sampling Line-Graph Colorings with Constant Extra Colors
Abstract
Let G be the line graph of a finite simple graph, with n≥1 vertices and maximum degree Δ. We prove that single-site Glauber dynamics for uniform proper q-colorings mixes in OΔ(nlog(n/ε)) steps for every integer q≥Δ+5. Our proof uses the Bochner framework of Chen and Liu (2026).
Related
- Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
- Colorings breaking prescribed families of graph automorphisms
- One Extra Dimension Suffices for the Complete-Graph Squared-Stress
- Counting edge-colorings of a complete graph avoiding a rainbow K4
BibTeX
@misc{haqi2026sampling,
title = {{Sampling Line-Graph Colorings with Constant Extra Colors}},
author = {Alireza Haqi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27440},
eprint = {2609.27440},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27440},
}
RIS
TY - UNPB
TI - Sampling Line-Graph Colorings with Constant Extra Colors
AU - Alireza Haqi
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27440
UR - https://arxiv.org/abs/2609.27440
AB - Let G be the line graph of a finite simple graph, with n≥1 vertices and maximum degree Δ. We prove that single-site Glauber dynamics for uniform proper q-colorings mixes in O_Δ(nlog(n/ε)) steps for every integer q≥Δ+5. Our proof uses the Bochner framework of Chen and Liu (2026).
ER -