On the chromatic number of graphs Academic Article

abstract

• Computing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0-1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program.

authors

• Butenko, Sergiy

published proceedings

• JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS

author list (cited authors)

• Butenko, S., Festa, P., & Pardalos, P. M.

complete list of authors

• Butenko, S||Festa, P||Pardalos, PM

publication date

• April 2001

published in

• JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS  Journal

keywords

• Combination Optimization
• Graph Coloring Problems
• Integer Programming
• Test Problems

start page

• 51

end page

• 67

volume

• 109

issue

• 1