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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
34
Citations
NaN
KQI