An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem

Kochenberger, Gary A., Glover, Fred, Alidaee, Bahram and Rego, Cesar
Annals of Operations Research Vol. 139, Issue 1, pp. 229 – 241.

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.