New bounds for the max-hBccut and chromatic number of a graph

We consider several semidefinite programming relaxations for the max-$k$-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite programming relaxation has a closed form expression that includes the largest Laplacian eigenvalue of the graph under consideration. This is the first known eigenvalue bound for the max-$k$-cut when $k>2$ that is applicable to … Read more

On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings

We investigate structural properties of the completely positive semidefinite cone, consisting of all the nxn symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of … Read more

An Axiomatic Duality Framework for the Theta Body and Related Convex Corners

Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are … Read more

Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone

We investigate the completely positive semidefinite cone $\mathcal{CS}_+^n$, a new matrix cone consisting of all $n\times n$ matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular we study relationships between this cone and the completely positive and doubly nonnegative cones, and between its dual cone and trace positive non-commutative … Read more

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

Approximating the Chromatic Number of a Graph by Semidefinite Programming

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(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number and the clique number of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either number by adding … Read more