  The vertex coloring problem asks for the minimum number of colors that can be
assigned to the vertices of a given graph such that each two adjacent vertices
get different colors. For this NP-hard problem, a variety of integer linear
programming (ILP) models have been suggested. Among them, the assignment based
and the partial-ordering based ILP models are attractive due to their
simplicity and easy extendability. Moreover, on sparse graphs, both models
turned out to be among the strongest exact approaches for solving the vertex
coloring problem. In this work, we suggest additional strengthening constraints
for the partial-ordering based ILP model, and show that they lead to improved
lower bounds of the corresponding LP relaxation. Our computational experiments
confirm that the new constraints are also leading to practical improvements. In
particular, we are able to find the optimal solution of a previously open
instance from the DIMACS benchmark set for vertex coloring problems

Discrete Mathematics