Finding independent sets in \(K_4\)-free 4-regular connected graphs (Q1386480): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1997.1772 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2081512224 / rank | |||
Normal rank |
Revision as of 20:36, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding independent sets in \(K_4\)-free 4-regular connected graphs |
scientific article |
Statements
Finding independent sets in \(K_4\)-free 4-regular connected graphs (English)
0 references
24 May 1998
0 references
Let \(G\) be a \(K_4\)-free 4-regular connected graph with \(v\) vertices. Then \(G\) contains an independent set of vertices of cardinality at least \((7v- 4)/26\). Furthermore, the proof will yield a polynomial-time algorithm which will return an independent set of cardinality at least \((7v- 4)/26\) for any such graph. A family of \(K_4\)-free 4-regular connected graphs with maximum independent set of cardinality \({3\over 11} v\) is provided, so that the asymptotically sharp lower bound lies between \({7\over 26}\) and \({3\over 11}\). We also provide a slight improvement over the best previously known result for triangle-free 5-regular graphs.
0 references
\(K_4\)-free 4-regular connected graph
0 references
independent set
0 references
polynomial-time algorithm
0 references
triangle-free 5-regular graphs
0 references