Finding independent sets in \(K_4\)-free 4-regular connected graphs

DOI10.1006/jctb.1997.1772zbMath0896.05031OpenAlexW2081512224MaRDI QIDQ1386480

Feng Lou, Stephen C. Locke

Publication date: 24 May 1998

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

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

zbMATH Keywords

independent setpolynomial-time algorithm\(K_4\)-free 4-regular connected graphtriangle-free 5-regular graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items

Bounded clique cover of some sparse graphs, Turán type results for distance graphs, On line graphs of subcubic triangle-free graphs, Maximum induced forests in graphs of bounded treewidth, Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs, Independence and matching number of some graphs, On the clique-transversal number in \({(\mathrm{claw},K_4)}\)-free 4-regular graphs, Independent sets in the union of two Hamiltonian cycles, The signed maximum-clique transversal number of regular graphs

Cites Work

• Independence in graphs with maximum degree four
• The edge chromatic difference sequence of a cubic graph
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Edge density and independence ratio in triangle-free graphs with maximum degree three
• Bipartite density and the independence ratio
• Some Ramsey-Type Numbers and the Independence Ratio
• Size and independence in triangle‐free graphs with maximum degree three
• Finding Independent Sets in Triangle-Free Graphs
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item