Max-Cut in Degenerate $H$-Free Graphs

Abstract

We obtain several lower bounds on the $\text{Max-Cut}$ of $d$-degenerate $H$-free graphs. Let $f(m,d,H)$ denote the smallest $\text{Max-Cut}$ of an $H$-free $d$-degenerate graph on $m$ edges. We show that $f(m,d,K_r)\ge \left(\frac{1}{2}+d^{-1+\hat{I}\text{c◯}(r^{-1})}\right)m$, generalizing a recent work of Carlson, Kolla, and Trevisan. We also give bounds on $f(m,d,H)$ when $H$ is a cycle, odd wheel, or a complete bipartite graph with at most 4 vertices on one side. We also show stronger bounds on $f(m,d,K_r)$ assuming a conjecture of Alon, Bollabas, Krivelevich, and Sudakov (2003). We conjecture that $f(m,d,K_r)=\left(\frac{1}{2}+\hat{I}{˜}_r(d^{-1/2})\right)m$ for every $r\ge 3$, and show that this conjecture implies the ABKS conjecture.

This paper has been superseded by arXiv:1810.10044