Induced Matchings in Subcubic Graphs
Felix Joos, Dieter Rautenbach, Thomas Sasse · SIAM Journal on Discrete Mathematics · 2014
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üller (SIAM J. Discrete Math., 26 (2012), pp. 1383--1411) and solves a conjecture of Henning and Rautenbach.