A semidefinite programming based heuristic for graph coloring

Igor Dukanovic (igor.matuni-mb.si)
Franz Rendl (franz.rendluni-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