pith. sign in

arxiv: 1708.03996 · v2 · pith:YNXB6YD4new · submitted 2017-08-14 · 🧮 math.CO

Cubic graphs with small independence ratio

classification 🧮 math.CO
keywords inftyalphaboundfracgraphsimprovedindependenceratio
0
0 comments X
read the original 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) := \lim\limits_{g \to \infty} 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\'oka improved it to $i(3,\infty) \ge 0.44533$ in 2016. Bollob\'as 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 0.454.$

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.