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.
Citation
Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, February 2007.