A lower bound on the acyclic matching number of subcubic graphs

DOI10.1016/J.DISC.2018.05.010zbMath1388.05151arXiv1710.10076OpenAlexW2963430299MaRDI QIDQ1637156

Dieter Rautenbach, Maximilian Fürst

Publication date: 7 June 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.10076

zbMATH Keywords

subcubic graphacyclic matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Connectivity (05C40)

Related Items (6)

Acyclic Matching in Some Subclasses of Graphs ⋮ Acyclic matchings in graphs of bounded maximum degree ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ Uniquely restricted matchings in subcubic graphs ⋮ Lower bounds on the uniquely restricted matching number ⋮ Approximating maximum acyclic matchings by greedy and local search strategies

Cites Work

• Unnamed Item
• Induced matchings in subcubic graphs without short cycles
• Matchings in graphs of odd regularity and girth
• Independent sets and matchings in subcubic graphs
• Maximum matchings in regular graphs of high girth
• Degenerate matchings and edge colorings
• Generalized subgraph-restricted matchings in graphs
• Tight bounds on maximal and maximum matchings
• Tight lower bounds on the size of a maximum matching in a regular graph
• Induced Matchings in Graphs of Bounded Maximum Degree
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• Induced matchings in cubic graphs
• Induced Matchings in Subcubic Graphs
• Paths, Trees, and Flowers

This page was built for publication: A lower bound on the acyclic matching number of subcubic graphs