Paper Info
Title
Acyclic matchings in graphs of bounded maximum degree
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)) 6n/delta(2), and we explain how to find such an acyclic matching in polynomial time. (C) 2022 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.disc.2022.112885
DISCRETE MATHEMATICS
Keywords
DocType
Volume
Acyclic matching
Journal
345
Issue
ISSN
Citations 
7
0012-365X
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Julien Baste11810.17
Fürst Maximilian200.34
Dieter Rautenbach3946138.87