Staton proved that every 3-regular triangle-free graph has independence ratio at least 5/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/30 - 2/15n, where n is the number of vertices in the graph. This is strictly larger than 5/14 for n>14. Furthermore, there is an infinite family of connected S-regular triangle-free graphs with independence ratio 11/30-1/15n, limiting much further improvement. The proof will yield a polynomial-time algorithm to find an independent set of cardinality at least (11n-4)/30. (C) 1995 Academic Press, Inc. [References: 11]
展开▼
