On the asymmetric representatives formulation for the vertex coloring problem |
| |
Authors: | Manoel Campêlo Victor A Campos |
| |
Institution: | Mestrado e Doutorado em Ciência da Computação, Universidade Federal do Ceará, Campus do Pici, Bloco 910, 60455-760 Fortaleza, CE, Brazil |
| |
Abstract: | We consider the vertex coloring problem, which can be stated as the problem of minimizing the number of labels that can be assigned to the vertices of a graph G such that each vertex receives at least one label and the endpoints of every edge are assigned different labels. In this work, the 0-1 integer programming formulation based on representative vertices is revisited to remove symmetry. The previous polyhedral study related to the original formulation is adapted and generalized. New versions of facets derived from substructures of G are presented, including cliques, odd holes and anti-holes and wheels. In addition, a new class of facets is derived from independent sets of G. Finally, a comparison with the independent sets formulation is provided. |
| |
Keywords: | Chromatic number Combinatorial problems Facets of polyhedra Graph coloring |
本文献已被 ScienceDirect 等数据库收录! |
|