Finding independent sets in K₄-free 4-regular connected graphs
Finding independent sets in \(K 4\)-free 4-regular connected graphs
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.
- The independence number of connected (claw, K₄)-free 4-regular graphs
- Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
- Finding Independent Sets in Triangle-Free Graphs
- 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
- The independence number in graphs of maximum degree three
- 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
- Bipartite density and the independence ratio
- Edge density and independence ratio in triangle-free graphs with maximum degree three
- Finding Independent Sets in Triangle-Free Graphs
- scientific article; zbMATH DE number 3664996 (Why is no real title available?)
- scientific article; zbMATH DE number 3675940 (Why is no real title available?)
- scientific article; zbMATH DE number 21730 (Why is no real title available?)
- scientific article; zbMATH DE number 3536160 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- Independence in graphs with maximum degree four
- Paths, Trees, and Flowers
- Size and independence in triangle‐free graphs with maximum degree three
- Some Ramsey-Type Numbers and the Independence Ratio
- The edge chromatic difference sequence of a cubic graph
- Degree multiplicities and independent sets in \(K_ 4\)-free graphs
- The independence number of connected (claw, K₄)-free 4-regular graphs
- Independent sets in \((P_4+P_4\),triangle)-free graphs
- Bounded clique cover of some sparse graphs
- On line graphs of subcubic triangle-free graphs
- Independence and matching number of some graphs
- On the clique-transversal number in \({(\mathrm{claw},K_4)}\)-free 4-regular graphs
- Turán type results for distance graphs
- Maximum induced forests in graphs of bounded treewidth
- Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
- Lower bounds on size and independence inK4-free graphs
- The signed maximum-clique transversal number of regular graphs
- Independent sets in the union of two Hamiltonian cycles
This page was built for publication: Finding independent sets in \(K_4\)-free 4-regular connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386480)
