A Polyhedral Approach for Graph Coloring1

We present an approach based on an integer programming formulation of the graph coloring problem. Our goal is to develop a model that removes some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the associated polytope. The theoretical results described here will be used to design an efficient Branch&Cut algorithm in a future work.