-

 

 

 




Optimization Online





 

A semidefinite programming based heuristic for graph coloring

Igor Dukanovic (igor.mat***at***uni-mb.si)
Franz Rendl (franz.rendl***at***uni-klu.ac.at)

Abstract: The Lovasz theta function is a well-known polynomial lower bound on the chromatic number. . Any near optimal solution of its semidefinite programming formulation carries valuable information on how to color the graph. A self-contained presentation of the role of this formulation in obtaining heuristics for the graph coloring problem is presented.

Keywords: Graph (vertex) coloring, Lovasz theta number

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation: Submitted to Discrete Applied Mathematics, Special Issue on Computational Methods in Graph Coloring.

Download:

Entry Submitted: 04/20/2005
Entry Accepted: 04/20/2005
Entry Last Modified: 01/03/2006

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society