Finding independent sets in \(K_4\)-free 4-regular connected graphs (Q1386480): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1006/jctb.1997.1772 / rank | |||
Property / DOI | |||
Property / DOI: 10.1006/JCTB.1997.1772 / rank | |||
Normal rank |
Latest revision as of 19:16, 10 December 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