Finding independent sets in \(K_4\)-free 4-regular connected graphs (Q1386480): Difference between revisions

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.