Induced Matchings in Graphs of Bounded Maximum Degree

2014/06/10 by Felix Joos, Joos, Felix · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1406.2440

openalex publication_date 2014/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a graph G, let ν_s(G) be the induced matching number of G. We prove that ν_s(G) ≥ \fracn(G)(\lceil\fracΔ2\rceil+1) (\lfloor\fracΔ2\rfloor+1) for every graph of sufficiently large maximum degree Δ and without isolated vertices. This bound is sharp. Moreover, there is polynomial-time algorithm which computes induced matchings of size as stated above.

Cited by

• Computational results on semistrong edge coloring of graphs
• Induced Matchings in Graphs of Maximum Degree 4

Related

• Induced matchings in graphs of degree at most 4
• Induced Matchings in Graphs of Maximum Degree 4
• An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs
• Some bounds on the maximum induced matching numbers of certain grids
• On Maximum Induced Matching Numbers of Special Grids