Computing the Grothendieck constant of some graph classes

Given a graph G = ([n],E) and w ∈ R^E, consider the integer program max x∈{±1}^n \sum_{ij∈E} w_{ij} x_i x_j and its canonical semidefinite programming relaxation max \sum_{ij∈E} w_{ij} v_i^T v_j , where the maximum is taken over all unit vectors v_i ∈ R^n. The integrality gap of this relaxation is known as the Grothendieck constant K(G) of G. We present a closed-form formula for the Grothendieck constant of K_5-minor free graphs and derive that it is at most 3/2. Moreover, we show that K(G) ≤ K(K_k) if the cut polytope of G is defined by inequalities supported by at most k points. Lastly, since the Grothendieck constant of K_n grows as O(log n), it is interesting to identify instances with large gap. However this is not the case for the clique-web inequalities, a wide class of valid inequalities for the cut polytope, whose integrality ratio is shown to be bounded by 3.