Back to Search
Start Over
Acyclic matchings in graphs of bounded maximum degree
- 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 :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2002.03649
- Document Type :
- Working Paper