Large Cuts with Local Algorithms on Triangle-Free Graphs

Juho Hirvonen, Joel Rybicki, Stefan Schmid +1

We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 +…