| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420805 | Discrete Applied Mathematics | 2008 | 10 Pages |
Abstract
The Lovász θθ-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. These heuristics could be useful for coloring medium sized graphs as numerical results on DIMACS benchmark graphs indicate.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Igor Dukanovic, Franz Rendl,