{"id":"arxiv/2606.08356","url":"https://arxiv.org/abs/2606.08356","tags":["math.OC"],"score":0,"title":"Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results","domain":"math.OC","source":"arxiv","authors":["Mingming Zheng","Roberto Baldacci","Fabio Furini","Qinghua Wu"],"reviews":0,"subject":"math.OC","summary":"This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm integrates enhanced pricing strategies based on Zero-Suppressed Binary Decision Diagrams (ZDDs) for solving the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic procedures and column generation, BPCOL+ reduces the size of the ZDD by applying maximal stable set reduction techniques that exploit alternative dual vectors. Computational experiments on the 137 DIMACS benchmark…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-06","reactions":{}}