On the Independence Number of Graphs with Maximum Degree 3

DOI10.1007/978-3-642-25870-1_22zbMath1341.05192OpenAlexW1921482839MaRDI 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 complexityindependent set problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Related Items (1)

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

This page was built for publication: On the Independence Number of Graphs with Maximum Degree 3