Induced matchings in subcubic graphs without short cycles

DOI10.1016/J.DISC.2013.10.009zbMath1279.05055OpenAlexW1998074097MaRDI QIDQ393187

Dieter Rautenbach, Michael A. Henning

Publication date: 16 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.disc.2013.10.009

zbMATH Keywords

induced matchingstrong chromatic indexstrong matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Acyclic matchings in graphs of bounded maximum degree ⋮ A lower bound on the acyclic matching number of subcubic graphs ⋮ A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number ⋮ Uniquely restricted matchings in subcubic graphs without short cycles ⋮ Degenerate matchings and edge colorings ⋮ Lower bounds on the uniquely restricted matching number ⋮ Strong chromatic index of subcubic planar multigraphs ⋮ Approximating weighted induced matchings ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ A characterization of graphs with given maximum degree and smallest possible matching number ⋮ Induced Matchings in Graphs of Bounded Maximum Degree ⋮ A characterization of graphs with given maximum degree and smallest possible matching number. II ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ A generalization of Petersen's matching theorem

Cites Work

• Unnamed Item
• Improved induced matchings in sparse graphs
• On induced matchings
• On distance-3 matchings and induced matchings
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Induced matchings in bipartite graphs
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• The strong chromatic index of a cubic graph is at most 10
• Induced matchings
• Incidence and strong edge colorings of graphs
• A bound on the strong chromatic index of a graph
• Induced matchings in intersection graphs.
• Maximum induced matchings of random cubic graphs
• Generalized subgraph-restricted matchings in graphs
• On maximum induced matchings in bipartite graphs
• Induced matchings in cubic graphs
• Induced Matchings in Subcubic Planar Graphs
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs

This page was built for publication: Induced matchings in subcubic graphs without short cycles