2008-07-01

# The operator $\Psi$ for the Chromatic Number of a Graph

## Publication

### Publication

*SIAM Journal on Optimization , Volume 19 - Issue 02 p. 572- 591*

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\'{a}sz 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.

Additional Metadata | |
---|---|

Keywords | (fractional) chromatic number, stability number, Lov\' asz theta number, semidefinite programming |

MSC | Semidefinite programming (msc 90C22), Combinatorial optimization (msc 90C27) |

THEME | Logistics (theme 3) |

Publisher | S.I.A.M. |

Journal | SIAM Journal on Optimization |

Project | Semidefinite programming and combinatorial optimization |

Citation |
Gvozdenovic, N, & Laurent, M. (2008). The operator $\Psi$ for the Chromatic Number of a Graph.
SIAM Journal on Optimization, 19(02), 572–591. |