Back to Search Start Over

Acyclic matchings in graphs of bounded maximum degree

Authors :
Baste, Julien
Fürst, Maximilian
Rautenbach, Dieter
Publication Year :
2020

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))\frac{6n}{\Delta^2},$ and we explain how to find such an acyclic matching in polynomial time.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2002.03649
Document Type :
Working Paper