MaxCut in graphs with sparse neighborhoods

Jinghua Deng, Jianfeng Hou, Siwei Lin +1

Let $G$ be a graph with $m$ edges and let $\mathrm{mc}(G)$ denote the size of a largest cut of $G$. The difference $\mathrm{mc}(G)-m/2$ is called the surplus $\mathrm{sp}(G)$ of $G…