Cubic graphs with small independence ratio (Q1733918): Difference between revisions

Summary: 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) := \lim\limits_{g \rightarrow \infty} i(r,g)\). Recently, several new lower bounds of \(i(3,\infty)\) were obtained. In particular, \textit{C. Hoppen} and \textit{N. Wormald} showed in [J. Comb. Theory, Ser. B 121, 367--397 (2016; Zbl 1348.05191)] that \(i(3, \infty) \geq 0.4375,\) and \textit{E. Csóka} et al. improved it to \(i(3,\infty) \geq 0.44533\) in [Random Struct. Algorithms 47, No. 2, 284--303 (2015; Zbl 1322.05106)]. \textit{B. Bollobas} proved the upper bound \(i(3,\infty) < \frac{6}{13}\) in [Proc. Am. Math. Soc. 83, 433--436 (1981; Zbl 0474.05057)], and \textit{B. D. McKay} improved it to \(i(3,\infty) < 0.45537\)in [Ars Comb. 23A, 179--185 (1987; Zbl 0644.05028)]. There were no improvements since then. In this paper, we improve the upper bound to \(i(3,\infty) \leq 0.454.\)