On the Independence Number of Graphs with Maximum Degree 3

DOI10.1007/978-3-642-25870-1_22zbMath1341.05192MaRDI QIDQ3104780

Fenghui Zhang, Iyad A. Kanj

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

zbMATH Keywords

parameterized complexity; independent set problem

Mathematics Subject Classification ID

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

Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs

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