Lower Bound for (Sum) Coloring Problem
This work addresses graph coloring optimization for theoretical computer science and operations research, with incremental improvements to benchmark results.
The paper tackled the Minimum Sum Coloring Problem by developing a new method to compute lower bounds via relaxation into an integer partition problem with constraints, improving lower bounds for 18 DIMACS benchmark graphs and proving optimality for 4 graphs by matching known upper bounds.
The Minimum Sum Coloring Problem is a variant of the Graph Vertex Coloring Problem, for which each color has a weight. This paper presents a new way to find a lower bound of this problem, based on a relaxation into an integer partition problem with additional constraints. We improve the lower bound for 18 graphs of standard benchmark DIMACS, and prove the optimal value for 4 graphs by reaching their known upper bound.