Cubic graphs with small independence ratio

Abstract

Let $i(r,g)$ denote the infimum of the ratio $\frac{\alpha (G)}{|V(G)|}$ over the $r$-regular graphs of girth at least $g$, where $\alpha (G)$ is the independence number of $G$, and let $i(r,\infty ):=\underset{g\to \infty }{\lim }i(r,g)$. Recently, several new lower bounds of $i(3,\infty )$ were obtained. In particular, Hoppen and Wormald showed in 2015 that $i(3,\infty )\ge 0.4375$, and Csóka improved it to $i(3,\infty )\ge 0.44533$ in 2016. Bollobás proved the upper bound $i(3,\infty )<\frac{6}{13}$ in 1981, and McKay improved it to $i(3,\infty )<0.45537$ in 1987. There were no improvements since then. In this paper, we improve the upper bound to $i(3,\infty )\le \mathrm{0.454.}$

21 pages, 1 figure, 2 tables

References in corpus (1)

• Independent sets and cuts in large-girth regular graphs

Cited by in corpus (1)

• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples