Induced Matchings in Subcubic Graphs
classification
🧮 math.CO
keywords
graphsinducedmatchingssubcubicdiscreteedgesmathplanar
read the original abstract
We prove that a cubic graph with $m$ edges has an induced matching with at least $m/9$ edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and M\"{u}ller (Induced matchings in subcubic planar graphs, SIAM J. Discrete Math. 26 (2012) 1383-1411) and solves a conjecture of Henning and Rautenbach (Induced matchings in subcubic graphs without short cycles, to appear in Discrete Math.).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.