Optimization Online


Approximating the Chromatic Number of a Graph by Semidefinite Programming

Nebojsa Gvozdenovic (nebojsa***at***cwi.nl)
Monique Laurent (monique***at***cwi.nl)

Abstract: We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an application, there is no polynomial time computable graph parameter nested between the fractional chromatic number $\chi^*(\cdot)$ and $\chi(\cdot)$ unless P=NP and, based on Motzkin-Straus formulation for $\alpha(G)$, we give quadratic and copositive programming formulations for $\chi(G)$. Under some mild assumption, $n/\beta(G)\le \Psi_\beta(G)$ but, while $n/\beta(G)$ remains below $\chi^*(G)$, $\Psi_\beta(G)$ can reach $\chi(G)$ (e.g., for $\beta(\cdot)=\alpha(\cdot)$). We define new lower bounds for $\chi(G)$ which we test on Hamming graphs and on some benchmark graphs. Our preliminary experimental results indicate that the new bounds can be much stronger than the classic bound $\vartheta ( \bar G ) $ (and its strengthenings obtained by adding nonnegativity and triangle inequalities).

Keywords: chromatic number, semidefinite programming, block-diagonalization, Terwilliger algebra

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Combinatorial Optimization

Citation: This is an old version. The paper was split and updated. Please see "The operator $\Psi$ for the Chromatic Number of a Graph" and "Computing the $\psi$ and $\Psi$ semidefinite programming bounds for the chromatic number"

Download: [Postscript][PDF]

Entry Submitted: 12/21/2005
Entry Accepted: 12/21/2005
Entry Last Modified: 02/24/2007

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