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).
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"
Article
View Approximating the Chromatic Number of a Graph by Semidefinite Programming