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.


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


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