Induced Matchings in Subcubic Planar Graphs

DOI10.1137/100808824zbMath1256.05191OpenAlexW4230263834MaRDI QIDQ4899067

Tobias Müller, Ross J. Kang, Matthias Mnich

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/induced-matchings-in-subcubic-planar-graphs(db2ca183-1f83-412d-9f4a-6c59bbaeef51).html

zbMATH Keywords

strong chromatic indexinduced matchingssubcubic planar graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Total dominating sequences in graphs ⋮ Total dominating sequences in trees, split graphs, and under modular decomposition ⋮ Induced matchings in subcubic graphs without short cycles ⋮ Degenerate matchings and edge colorings ⋮ Strong chromatic index of subcubic planar multigraphs ⋮ Approximating weighted induced matchings ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem

This page was built for publication: Induced Matchings in Subcubic Planar Graphs