11/30 (Finding large independent sets in connected triangle-free 3- regular graphs) (Q1898730)

Staton proved that every 3-regular triangle-free graph has independence ratio at least \({5\over 14}\) and displayed a graph on 14 vertices which achieved exactly this ratio. We show that the independence ratio for connected 3-regular triangle-free graphs must be at least \({11\over 30}- {2\over 15n}\), where \(n\) is the number of vertices in the graph. This is strictly larger than \({5\over 14}\) for \(n> 14\). Furthermore, there is an infinite family of connected 3-regular triangle-free graphs with independence ratio \({11\over 30}- {1\over 15n}\), limiting much further improvement. The proof will yield a polynomial-time algorithm to find an independent set of cardinality at least \({11n- 4\over 30}\).