Induced Matchings in Graphs of Bounded Maximum Degree

DOI10.1137/16M1058078zbMath1346.05234arXiv1406.2440MaRDI QIDQ2826215

Felix Joos

Publication date: 10 October 2016

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

Full work available at URL: https://arxiv.org/abs/1406.2440

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 (11)

Acyclic matchings in graphs of bounded maximum degree ⋮ A lower bound on the acyclic matching number of subcubic graphs ⋮ A Stronger Bound for the Strong Chromatic Index ⋮ Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier ⋮ Lower bounds on the uniquely restricted matching number ⋮ Approximating weighted induced matchings ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ Some bounds on the maximum induced matching numbers of certain grids ⋮ Recent progress on strong edge-coloring of graphs ⋮ The \(\text{v} \)-number of monomial ideals

Cites Work

• Unnamed Item
• Unnamed Item
• A stronger bound for the strong chromatic index (extended abstract)
• Induced matchings in subcubic graphs without short cycles
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• Induced Matchings in Subcubic Graphs
• Paths, Trees, and Flowers
• Induced Matchings in Graphs of Degree at Most 4

This page was built for publication: Induced Matchings in Graphs of Bounded Maximum Degree