11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)

DOI10.1006/jctb.1995.1043zbMath0828.05032OpenAlexW2065134396MaRDI QIDQ1898730

Kathryn Fraughnaugh, Stephen C. Locke

Publication date: 18 December 1995

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1995.1043

zbMATH Keywords

independent setpolynomial-time algorithmindependence ratio3-regular triangle-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Turán type results for distance graphs ⋮ On line graphs of subcubic triangle-free graphs ⋮ Finding independent sets in \(K_4\)-free 4-regular connected graphs ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs ⋮ Relating the independence number and the dissociation number ⋮ Independent sets and matchings in subcubic graphs ⋮ On the tightness of the \(\frac {5}{14}\) independence ratio ⋮ Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three ⋮ Independent sets in triangle-free cubic planar graphs ⋮ The independence number in graphs of maximum degree three ⋮ On the Independence Number of Graphs with Maximum Degree 3 ⋮ Fractional Chromatic Number, Maximum Degree, and Girth

This page was built for publication: 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)