On the Independence Number of Graphs with Maximum Degree 3
From MaRDI portal
Publication:3104780
DOI10.1007/978-3-642-25870-1_22zbMath1341.05192MaRDI QIDQ3104780
Publication date: 16 December 2011
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_22
05C35: Extremal problems in graph theory
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C07: Vertex degrees
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The independence number in graphs of maximum degree three
- Some simplified NP-complete graph problems
- On approximation properties of the independent set problem for low degree graphs
- 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
- A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Some Ramsey-Type Numbers and the Independence Ratio
- Size and independence in triangle‐free graphs with maximum degree three
- A new proof of the independence ratio of triangle-free cubic graphs