The operator $\Psi$ for the Chromatic Number of a Graph

Nebojsa Gvozdenovic (nebojsacwi.nl)
Monique Laurent (moniquecwi.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\left( {\ol G} \right)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\alpha (\ol 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. Moreover, based on Motzkin-Straus formulation for $\alpha(G)$, we give (quadratically constrained) 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 also define new polynomial time computable lower bounds for $\chi(G)$, improving the classic Lov\' asz theta number (and its strengthenings obtained by adding nonnegativity and triangle inequalities); experimental results on Hamming graphs, Kneser graphs and DIMACS benchmark graphs will be given in the follow-up paper.

Keywords: (fractional) chromatic number, stability number, Lov\' asz theta number, semidefinite programming

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, February 2007.

Download: [PDF]

Entry Submitted: 02/24/2007
Entry Accepted: 02/26/2007
Entry Last Modified: 12/11/2007

Modify/Update this entry