- Approximating the Chromatic Number of a Graph by Semidefinite Programming 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(\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/2005Entry Accepted: 12/21/2005Entry Last Modified: 02/24/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.