On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs

DOI10.1016/j.tcs.2019.11.020zbMath1442.05175arXiv1807.08981OpenAlexW2991333895WikidataQ126661374 ScholiaQ126661374MaRDI QIDQ2283036

Maximilian Fürst, Dieter Rautenbach

Publication date: 27 December 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.08981

zbMATH Keywords

uniquely restricted matchinginduced matchingstrong matching

Mathematics Subject Classification ID

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

Cites Work

• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum 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 the approximability of the maximum induced matching problem
• Equality of distance packing numbers
• The graphs with maximum induced matching and maximum matching the same size
• On the Maximum Uniquely Restricted Matching for Bipartite Graphs
• Graphs in which some and every maximum matching is uniquely restricted
• Uniquely restricted matchings

This page was built for publication: On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs