A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs
share
In this paper we study the problem of finding large cuts in K_r-free graphs with max degree d. We show that such graphs always have cuts which cut a 1/2+Ω(1/d^1-1/d^r-2) fraction of edges. This generalizes known results for K_3-free graphs. A key component of this result is showing that graphs with few triangles also have non-trivially good cuts.
READ FULL TEXT