Induced Matchings in Graphs of Degree at Most 4

DOI10.1137/140986980zbMath1329.05245arXiv1407.7604OpenAlexW2253797408MaRDI QIDQ5743551

Viet Hang Nguyen, Felix Joos

Publication date: 5 February 2016

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

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

zbMATH Keywords

edge coloringindependent setinduced 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Acyclic matchings in graphs of bounded maximum degree ⋮ A Stronger Bound for the Strong Chromatic Index ⋮ Approximating weighted induced matchings ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ Some bounds on the maximum induced matching numbers of certain grids ⋮ Induced Matchings in Graphs of Bounded Maximum Degree ⋮ Recent progress on strong edge-coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A stronger bound for the strong chromatic index (extended abstract)
• Irredundancy in circular arc graphs
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Maximum induced matchings for chordal graphs in linear time
• NP-completeness of some generalizations of the maximum matching problem
• The strong chromatic index of a cubic graph is at most 10
• Induced matchings
• A bound on the strong chromatic index of a graph
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• On the approximability of the maximum induced matching problem
• Finding a maximum induced matching in weakly chordal graphs
• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• New results on induced matchings
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Induced Matchings in Graphs of Bounded Maximum Degree
• Induced matchings in cubic graphs
• Induced Matchings in Subcubic Planar Graphs
• Induced Matchings in Subcubic Graphs
• Paths, Trees, and Flowers

This page was built for publication: Induced Matchings in Graphs of Degree at Most 4