The independence number in graphs of maximum degree three

DOI10.1016/J.DISC.2007.10.029zbMath1219.05120OpenAlexW2029614947MaRDI QIDQ998471

Dieter Rautenbach, Ingo Schiermeyer, Michael A. Henning, Jochen Harant

Publication date: 28 January 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00012968/IfM_Preprint_M_07_15.pdf

zbMATH Keywords

triangleindependencecubic graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Bounded clique cover of some sparse graphs ⋮ New bounds on the independence number of connected graphs ⋮ Independent sets and matchings in subcubic graphs ⋮ A rough set method for the vertex cover problem in graph theory ⋮ An improved lower bound on the independence number of a graph ⋮ Independence, odd girth, and average degree ⋮ Bounds on the independence number of a graph in terms of order, size and maximum degree ⋮ Minimum \(k\)-path vertex cover ⋮ On the Independence Number of Graphs with Maximum Degree 3 ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ The \(k\)-path vertex cover of rooted product graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the tightness of the \(\frac {5}{14}\) independence ratio
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• 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
• A new proof of the independence ratio of triangle-free cubic graphs

This page was built for publication: The independence number in graphs of maximum degree three