Computing the Grothendieck constant of some graph classes

Given a graph $G=([n],E)$ and $w\in {\mathbb{R}}^E$, consider the integer program ${\max }_{}{\sum }_{ij\in E}{w}_{ij}{x}_i{x}_j$ and its canonical semidefinite programming relaxation $\max {\sum }_{ij\in E}{w}_{ij}{v}_i^T{v}_j$, where the maximum is taken over all unit vectors $v_i\in {\mathbb{R}}^n$. The integrality gap of this relaxation is known as the Grothendieck constant $\text{ka}(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 $\text{ka}(G)\le \text{ka}(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 $\mathrm{\Theta }(\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.