Acyclic matchings in graphs of bounded maximum degree

DOI10.1016/j.disc.2022.112885zbMath1489.05114arXiv2002.03649OpenAlexW3004873882WikidataQ114190528 ScholiaQ114190528MaRDI QIDQ2138980

Maximilian Fürst, Julien Baste, Dieter Rautenbach

Publication date: 17 May 2022

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

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

zbMATH Keywords

\(\Delta\)-regular graphacyclic matching number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Cites Work

• Induced matchings in subcubic graphs without short cycles
• NP-completeness of some generalizations of the maximum matching problem
• A lower bound on the acyclic matching number of subcubic graphs
• Degenerate matchings and edge colorings
• 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
• Generalized subgraph-restricted matchings in graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• On some hard and some tractable cases of the maximum acyclic matching problem
• On the hardness of deciding the equality of the induced and the uniquely restricted matching number
• The graphs with maximum induced matching and maximum matching the same size
• Induced Matchings in Graphs of Bounded Maximum Degree
• ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
• Induced Matchings in Subcubic Graphs
• Induced Matchings in Graphs of Degree at Most 4

This page was built for publication: Acyclic matchings in graphs of bounded maximum degree