Photo from wikipedia
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… Click to show full 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.
Keywords:
maximum degree;
acyclic matchings;
graphs bounded;
bounded maximum;
matchings graphs
Journal Title: Discrete Mathematics
Year Published: 2022
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Discrete Mathematics
Year Published: 2022
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!