An integer programming approach to b-coloring |
| |
Affiliation: | 1. University of Illinois Urbana-Champaign, Department of Industrial and Enterprise Systems Engineering, United States;2. RWTH Aachen University, School of Business and Economics, Germany;3. University of Waterloo, Department of Combinatorics & Optimization, Canada |
| |
Abstract: | In the b-coloring problem, we aim to assign colors from a set to the vertices of a graph in such a way that adjacent vertices do not receive the same color, and for every we have a -colored vertex in such that every color in is assigned to at least one of ’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. |
| |
Keywords: | b-coloring Integer programming Facets Cutting planes |
本文献已被 ScienceDirect 等数据库收录! |
|