We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute. To establish this ... more >>>

It is a known approach to translate propositional formulas into systems of polynomial inequalities and to consider proof systems for the latter ones. The well-studied proof systems of this kind are the Cutting Planes proof system (CP) utilizing linear inequalities and the Lovasz-Schrijver calculi (LS) utilizing quadratic inequalities. We introduce ... more >>>