A lower bound on the acyclic matching number of subcubic graphs

2017/10/27 by Maximilian Fürst, Dieter Rautenbach, Fürst, M. +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1710.10076

openalex publication_date 2017/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The acyclic matching number of a graph G is the largest size of an acyclic matching in G, that is, a matching M in G such that the subgraph of G induced by the vertices incident to an edge in M is a forest. We show that the acyclic matching number of a connected subcubic graph G with m edges is at least m/6 except for two small exceptions.

Citations

• Degenerate Matchings and Edge Colorings

Cited by

• A Parameterized Perspective on Uniquely Restricted Matchings
• Some bounds on the uniquely restricted matching number

Related

• Acyclic matchings in graphs of bounded maximum degree
• Parameterized Results on Acyclic Matchings with Implications for Related Problems
• On lower bounds for the matching number of subcubic graphs
• Induced Matchings in Subcubic Graphs
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs