Name
Abstract | ||
|---|---|---|
We prove that every 3-regular, n-vertex simple graph with sufficiently large girth contains an independent set of size at least 0.4361n. The best known bound is 0.4352n. In fact, computer simulation suggests that the bound our method provides is about 0.438n. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/rsa.20547 | Random Structures & Algorithms |
Keywords | Field | DocType |
independent set,independence ratio,regular graph,large girth,random regular graph,regular tree,factor of i.i.d.,invariant Gaussian process | Odd graph,Discrete mathematics,Combinatorics,Strongly regular graph,Moore graph,k-edge-connected graph,Foster graph,Independent set,Symmetric graph,Triangle-free graph,Mathematics | Journal |
Volume | Issue | ISSN |
47 | 2 | Random Structures & Algorithms Volume 47, Issue 2, pages 284-303,
2015 |
Citations | PageRank | References |
8 | 0.65 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Endre Csóka | 1 | 44 | 6.42 |
| Balazs Gerencser | 2 | 30 | 7.69 |
| Viktor Harangi | 3 | 10 | 2.53 |
| Bálint Virág | 4 | 22 | 1.63 |