Cubic graphs with small independence ratio

Research output: Contribution to journalArticlepeer-review


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 (US)
Article numberP1.43
Pages (from-to)1-22
Number of pages22
JournalElectronic Journal of Combinatorics
Issue number1
StatePublished - 2019

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Cubic graphs with small independence ratio'. Together they form a unique fingerprint.

Cite this