  We devise a new formulation for the vertex coloring problem. Different from
other formulations, decision variables are associated with the pairs of
vertices. Consequently, colors will be distinguishable. Although the objective
function is fractional, it can be replaced by a piece-wise linear convex
function. Numerical experiments show that our formulation has significantly
good performance for dense graphs.
