  


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 MotzkinStraus 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, blockdiagonalization, Terwilliger algebra Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semidefinite 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/2005 Modify/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  