论文标题
最大程度的图表中的无环匹配
Acyclic matchings in graphs of bounded maximum degree
论文作者
论文摘要
如果$ g $中匹配的$ m $是无环的，那么如果一组$ g $的子图是$ m $的一组$ g $的$ g $。我们证明，每个具有$ n $顶点的图形，最多最高$δ$，并且没有孤立的顶点，都具有至少$（1-o（1-o（1））\ frac {6n} {Δ^2} {δ^2} $的无环匹配，我们可以解释如何在多物质元素中找到这样的无环匹配。
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))\frac{6n}{Δ^2},$ and we explain how to find such an acyclic matching in polynomial time.
