We present a Branch-and-Cut algorithm for the graph coloring problem.
In a previous work, we studied the facet estructure of the
0/1-polytope associated with an integer programming formulation of the
graph coloring problem. Based on these theoretical results a
Branch-and-Cut algorithm is developed. Our computational experiences
compare favorably with the well-known exact graph coloring algorithm