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) \geqslant 0.4375,$ and Csóka improved it to $i(3,\infty) \geqslant 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) \leqslant 0.454.$
@article{10_37236_7272,
author = {J\'ozsef Balogh and Alexandr Kostochka and Xujun Liu},
title = {Cubic graphs with small independence ratio},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/7272},
zbl = {1409.05079},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7272/}
}
TY - JOUR
AU - József Balogh
AU - Alexandr Kostochka
AU - Xujun Liu
TI - Cubic graphs with small independence ratio
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7272/
DO - 10.37236/7272
ID - 10_37236_7272
ER -
%0 Journal Article
%A József Balogh
%A Alexandr Kostochka
%A Xujun Liu
%T Cubic graphs with small independence ratio
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7272/
%R 10.37236/7272
%F 10_37236_7272
József Balogh; Alexandr Kostochka; Xujun Liu. Cubic graphs with small independence ratio. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7272
