A characterization of well-indumatchable graphs having girth greater than seven

DOI10.1016/J.DAM.2022.06.041zbMath1497.05216OpenAlexW4285585236MaRDI QIDQ2172407

Michael D. Plummer, Arthur S. Finbow, Bert L. Hartnell

Publication date: 15 September 2022

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

Full work available at URL: https://doi.org/10.1016/j.dam.2022.06.041

zbMATH Keywords

matchinggirthinduced matchingstrong chromatic indexleafstrong edge coloringstrong matchingstemdouble starco-NP-completenessequimatchable graphsdistance 2 matchingsingle starwell-indumatchable graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Well-indumatched Trees and Graphs of Bounded Girth

Cites Work

• Unnamed Item
• Unnamed Item
• Graphs with maximal induced matchings of the same size
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• On the computational complexity of strong edge coloring
• New results on maximum induced matchings in bipartite graphs and beyond
• New results on induced matchings
• Strong edge-colouring and induced matchings

This page was built for publication: A characterization of well-indumatchable graphs having girth greater than seven