Fast sampling method improves graph coloring with few extra colors
Sampling Line-Graph Colorings with Constant Extra Colors
Data Structures and Algorithms
Summary
Graph coloring is a way to assign colors to connections so that no overlapping ones share the same color. The paper looks at a type of graph called a line graph and shows how a random process called Glauber dynamics can quickly find valid colorings using only a few more colors than the maximum connections each point has. The authors use a mathematical tool known as the Bochner framework to prove this speed. This helps understand the efficiency of coloring algorithms for complex networks.
What this means in practice
- •For network engineers: Guarantee efficient scheduling and resource assignment in networks modeled by line graphs with minimal extra resources.
- •For optimization software developers: Design faster algorithms for sampling feasible solutions in combinatorial optimization problems involving line graphs.
A theory result. No direct application yet.
Authors
Alireza Haqi
Abstract
Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $Δ$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_Δ(n\log(n/\varepsilon))$ steps for every integer $q\geqΔ+5$. Our proof uses the Bochner framework of Chen and Liu (2026).