Semidefinite approximations for bicliques and biindependent pairs

\(\) We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be … Read more

Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

Lov\’ asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have … Read more