Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming
Charles A. Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan · SIAM Journal on Discrete Mathematics · 2021
For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming, to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.