Acyclic matchings in graphs of bounded maximum degree

DOI10.1016/J.DISC.2022.112885MaRDI QIDQ2138980zbMATH OpenOpenAlexWikidataFDO

Authors Julien Baste, Maximilian Fürst, 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

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

Abstract: A matching $M$ in a graph $G$ is acyclic if the subgraph of $G$ induced by the set of vertices that are incident to an edge in $M$ is a forest. We prove that every graph with $n$ vertices, maximum degree at most $Delta$, and no isolated vertex, has an acyclic matching of size at least $(1-o(1))frac6nDelt{a}^2,$ and we explain how to find such an acyclic matching in polynomial time.

Recommendations

• A lower bound on the acyclic matching number of subcubic graphs
• Acyclic matchings in subclasses of bipartite graphs
• Acyclic matching in some subclasses of graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Induced matchings in graphs of bounded maximum degree

Cites work

• A lower bound on the acyclic matching number of subcubic graphs
• Acyclic matchings in subclasses of bipartite 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
• Induced matchings in graphs of bounded maximum degree
• Induced matchings in graphs of degree at most 4
• Induced matchings in subcubic graphs
• Induced matchings in subcubic graphs without short cycles
• New results on maximum induced matchings in bipartite graphs and beyond
• NP-completeness of some generalizations of the maximum matching problem
• 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

Cited in

(11)

• Degenerate matchings and edge colorings
• Generalized subgraph-restricted matchings in graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Acyclic matchings
• Acyclic matching in some subclasses of graphs
• Matching for Graphs of Bounded Degree
• Acyclic matchings in subclasses of bipartite graphs
• Maximum acyclic and fragmented sets in regular graphs
• Parameterized Results on Acyclic Matchings with Implications for Related Problems
• Parameterized results on acyclic matchings with implications for related problems
• Structural parameterizations for induced and acyclic matching

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138980)