Induced matchings in subcubic planar graphs

Kang, Ross; Mnich, Matthias; Müller, Tobias

R.J. Kang (Ross), M. Mnich (Matthias) and T. Müller (Tobias)

2012

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.

Additional Metadata
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)
Publisher	S.I.A.M.
Journal	SIAM Journal on Discrete Mathematics
Organisation	Networks and Optimization
Citation APA Style AAA Style APA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	Kang, R., Mnich, M., & Müller, T. (2012). Induced matchings in subcubic planar graphs. SIAM Journal on Discrete Mathematics, 26(3), 1383–1411.

Free Full Text ( Final Version )

Additional Files
Publisher Version

Induced matchings in subcubic planar graphs

Publication

Publication

Address

CWI researchers

Questions or comments?

Induced matchings in subcubic planar graphs

Publication

Publication

Workflow

Workflow

Add Content