Facets of the graph coloring polytope. (English) Zbl 1013.90097

Coll, Pablo; Marenco, Javier; Méndez Díaz, Isabel; Zabala, Paula

Ann. Oper. Res. 116, 79-90 (2002).

Summary: We present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.

MSC:

90C10	Integer programming
05C15	Coloring of graphs and hypergraphs
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

graph coloring; integer programming; facets of polyhedra