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

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Import241208061232 (talk | contribs)
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1006/jctb.1997.1772 / rank
Normal 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
    0 references
    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

    Identifiers