Independent sets and cuts in large-girth regular graphs

Endre Csóka

We present a local algorithm producing an independent set of expected size $0.44533n$ on large-girth 3-regular graphs and $0.40407n$ on large-girth 4-regular graphs. We also constr…