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 language | English |
|---|---|
| Article number | P1.43 |
| Pages (from-to) | 1-22 |
| Number of pages | 22 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 26 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2019 |
| Externally published | Yes |