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 (9)

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

This page was built for publication: Finding independent sets in \(K_4\)-free 4-regular connected graphs