Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization
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