A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs

10/23/2018
by   Charles Carlson, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset