Optimization Online


Semidefinite programming relaxations for graph coloring and maximal clique problems

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

Abstract: The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number and the clique number of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either number by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups.

Keywords: Lovasz theta number, chromatic number, clique number, cutting planes

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: To appear in Mathematical Programming B.


Entry Submitted: 03/02/2005
Entry Accepted: 03/02/2005
Entry Last Modified: 05/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