Induced matchings in subcubic planar graphs
SIAM Journal on Discrete Mathematics , Volume 26 - Issue 3 p. 1383- 1411
We present a linear-time algorithm that, given a planar graph with m edges and maximum degree 3, finds an induced matching of size at least m/9. This is best possible.
|Keywords||induced matchings, subcubic planar graphs, strong chromatic index|
|MSC||Factorization, matching, partitioning, covering and packing (msc 05C70), Graph algorithms (msc 05C85), Graph theory (including graph drawing) (msc 68R10)|
|THEME||Logistics (theme 3)|
|Journal||SIAM Journal on Discrete Mathematics|
Kang, R.J, Mnich, M, & Müller, T. (2012). Induced matchings in subcubic planar graphs. SIAM Journal on Discrete Mathematics, 26(3), 1383–1411.