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

DOI10.1006/JCTB.1995.1043zbMATH Open0828.05032OpenAlexW2065134396MaRDI QIDQ1898730FDOQ1898730

Authors: Kathryn Fraughnaugh, S. 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

Recommendations

• Large independent sets in triangle-free cubic graphs: beyond planarity
• Large independent sets in triangle-free planar graphs
• Large independent sets in triangle-free planar graphs
• Finding Independent Sets in Triangle-Free Graphs
• Finding Large Independent Sets in Graphs and Hypergraphs
• On the third largest number of maximal independent sets of graphs
• On graphs with the third largest number of maximal independent sets
• Minimizing the number of independent sets in triangle-free regular graphs
• Large independent sets in regular graphs of large girth
• The number of maximal independent sets in connected triangle-free graphs

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cited In (18)

• Independent sets and matchings in subcubic graphs
• Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
• Finding large 3-free sets. I. The small \(n\) case
• Title not available (Why is that?)
• Lower bounds on the size of maximum independent sets and matchings in hypergraphs of rank three
• The independence number in graphs of maximum degree three
• Almost all triangle-free triple systems are tripartite
• On line graphs of subcubic triangle-free graphs
• Independence number of 2-factor-plus-triangles graphs
• Independence ratio and random eigenvectors in transitive graphs
• Relating the independence number and the dissociation number
• On the Independence Number of Graphs with Maximum Degree 3
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Turán type results for distance graphs
• Independent sets in triangle-free cubic planar graphs
• Fractional chromatic number, maximum degree, and girth
• On the tightness of the \(\frac {5}{14}\) independence ratio

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898730)