TY - JOUR
T1 - Cubic graphs with small independence ratio
AU - Balogh, József
AU - Kostochka, Alexandr
AU - Liu, Xujun
N1 - Publisher Copyright:
© The authors.
PY - 2019
Y1 - 2019
N2 - Let i(r, g) denote the infimum of the ratio [formula presente] over the r-regular graphs of girth at least g, where α(G) is the independence number of G, and let i(r, ∞):=g→∞lim i(r, g). Recently, several new lower bounds of i(3, ∞) were obtained. In par-ticular, Hoppen and Wormald showed in 2015 that i(3, ∞) ≥ 0.4375, and Csóka improved it to i(3, ∞) ≥ 0.44533 in 2016. Bollobás proved the upper bound i(3, ∞) <[formulapresented] in 1981, and McKay improved it to i(3, ∞) < 0.45537in 1987. There were no improvements since then. In this paper, we improve the upper bound to i(3, ∞) ≤ 0.454.
AB - Let i(r, g) denote the infimum of the ratio [formula presente] over the r-regular graphs of girth at least g, where α(G) is the independence number of G, and let i(r, ∞):=g→∞lim i(r, g). Recently, several new lower bounds of i(3, ∞) were obtained. In par-ticular, Hoppen and Wormald showed in 2015 that i(3, ∞) ≥ 0.4375, and Csóka improved it to i(3, ∞) ≥ 0.44533 in 2016. Bollobás proved the upper bound i(3, ∞) <[formulapresented] in 1981, and McKay improved it to i(3, ∞) < 0.45537in 1987. There were no improvements since then. In this paper, we improve the upper bound to i(3, ∞) ≤ 0.454.
UR - http://www.scopus.com/inward/record.url?scp=85090793736&partnerID=8YFLogxK
U2 - 10.37236/7272
DO - 10.37236/7272
M3 - Article
AN - SCOPUS:85090793736
SN - 1077-8926
VL - 26
SP - 1
EP - 22
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 1
M1 - P1.43
ER -