Finding independent sets in \(K_4\)-free 4-regular connected graphs
From MaRDI portal
Publication:1386480
DOI10.1006/jctb.1997.1772zbMath0896.05031OpenAlexW2081512224MaRDI QIDQ1386480
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
independent setpolynomial-time algorithm\(K_4\)-free 4-regular connected graphtriangle-free 5-regular graphs
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