Optimization Online


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

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\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

  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