- The operator $\Psi$ for the Chromatic Number of a Graph 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\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. Keywords: (fractional) chromatic number, stability number, Lov\' asz theta number, semidefinite programming Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming Citation: Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, February 2007. Download: [PDF]Entry Submitted: 02/24/2007Entry Accepted: 02/26/2007Entry Last Modified: 12/11/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.