Approximating the Chromatic Number of a Graph by Semidefinite Programming
Nebojsa Gvozdenovic (nebojsacwi.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"
Entry Submitted: 12/21/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|