On graphs with induced matching number almost equal to matching number

DOI10.1016/j.endm.2015.07.003zbMath1347.05155OpenAlexW2206694218MaRDI QIDQ324703

Dieter Rautenbach, Uéverton dos Santos Souza, Marcio Antônio Duarte, Felix Joos, Lucia Draque Penso

Publication date: 17 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.003

zbMATH Keywords

fixed parameter tractabilityinduced matchingstrong matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• The graphs with maximum induced matching and maximum matching the same size

This page was built for publication: On graphs with induced matching number almost equal to matching number