11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
type: Item
instance of: scholarly article
title: 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
zbMATH Open document ID: 0828.05032
author: Kathryn Fraughnaugh
author: S. C. Locke
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-12-18T00:00:00Z
review text: 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}\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 798757
zbMATH Keywords: 3-regular triangle-free graph
zbMATH Keywords: independence ratio
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: independent set
MaRDI profile type: Publication
full work available at URL: jctb.1995.1043
OpenAlex ID: W2065134396
DOI: 10.1006/JCTB.1995.1043
Recommended article: Large independent sets in triangle-free cubic graphs: beyond planarity
Recommended article: Large Independent Sets in Triangle-Free Planar Graphs
Recommended article: Finding Independent Sets in Triangle-Free Graphs
Recommended article: Finding Large Independent Sets in Graphs and Hypergraphs
Recommended article: On the third largest number of maximal independent sets of graphs
Recommended article: On graphs with the third largest number of maximal independent sets
Recommended article: Minimizing the number of independent sets in triangle-free regular graphs
Recommended article: Large independent sets in regular graphs of large girth
Recommended article: The number of maximal independent sets in connected triangle-free graphs
description: scientific article; zbMATH DE number 798757