Cubic graphs with small independence ratio

József Balogh*, Alexandr Kostochka, Xujun Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article numberP1.43
Pages (from-to)1-22
Number of pages22
JournalElectronic Journal of Combinatorics
Volume26
Issue number1
DOIs
Publication statusPublished - 2019
Externally publishedYes

Cite this