2020/02/10 by Baste, Julien, Fürst, Maximilian, Rautenbach, Dieter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2002.03649
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 Δ, and no isolated vertex, has an acyclic matching of size at least (1-o(1))(6n)/(Δ2), and we explain how to find such an acyclic matching in polynomial time.