2007-02-01

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

## Publication

### Publication

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 | |
---|---|

, , , | |

, | |

Mathematical Programming Society | |

Optimization Online | |

Semidefinite programming and combinatorial optimization | |

Organisation | Networks and Optimization |

Gvozdenovic, N., & Laurent, M. (2007). The operator $\Psi$ for the Chromatic Number of a Graph. Optimization Online. Mathematical Programming Society. |