Finding Independent Sets in Triangle-Free Graphs

DOI10.1137/S0895480194266434MaRDI QIDQ4717575zbMATH OpenOpenAlexFDO

Authors Kathryn Fraughnaugh, S. C. Locke

Publication date 1 December 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480194266434

zbMATH Keywords

efficient algorithmindependent settriangle-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Counting independent sets in triangle-free graphs
• Independent dominating sets in triangle-free graphs
• Independent sets in graphs with triangles
• Minimizing the number of independent sets in triangle-free regular graphs
• Independent sets in triangle-free cubic planar graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Finding independent sets in unions of perfect graphs
• Independent domination in triangle-free graphs
• scientific article; zbMATH DE number 5593359
• Counting independent sets in tricyclic graphs

Cited in

(12)

• Independent sets in graphs with triangles
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• On the complexity of the independent set problem in triangle graphs
• How to guard orthogonal polygons: diagonal graphs and vertex covers
• Independent dominating and neighborhood sets in triangular graphs
• Turán type results for distance graphs
• Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
• Independent dominating sets in triangle-free graphs
• scientific article; zbMATH DE number 1107725 (Why is no real title available?)
• Independent triangles covering given vertices of a graph

This page was built for publication: Finding Independent Sets in Triangle-Free Graphs

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