Description

We consider the problem of finding large cuts in graphs that contain no small cliques. We show that for any r >= 3, every k_r-free graphs with maximum degree d has a cut that cuts at least a 1/2 + Ω(1/d^{1-1/2^{r-2}}) fraction of its edges. This generalizes a result of Shearer that shows every triangle-free d-regular graph has a cut that cuts at least a 1/2 + Ω(1/\sqrt{d}) fraction of its edges. Our proof yields a randomized polynomial-time algorithm.