lov\’ asz theta number

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

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    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 … Read more

    Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Recently we investigated in “The operator $\Psi$ for the Chromatic Number of a Graph” hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. In particular, we introduced two hierarchies of lower bounds, the `$\psi$’-hierarchy converging to the fractional chromatic number, and the `$\Psi$’-hierarchy converging to the chromatic number of a graph. … Read more