Induced Matchings in Subcubic Graphs

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 Muller (SIAM J. Discrete Math., 26 (2012), pp. 1383--1411) and solves a conjecture of Henning and Rautenbach.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    12
    References
    34
    Citations
    NaN
    KQI
    []