×

zbMATH — the first resource for mathematics

Facets of the graph coloring polytope. (English) Zbl 1013.90097
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
PDF BibTeX XML Cite
Full Text: DOI