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

DOI10.1016/J.DAM.2022.06.041MaRDI QIDQ2172407zbMATH OpenOpenAlexFDO

Authors Arthur S. Finbow, Michael D. Plummer, 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

co-NP-completenessdistance 2 matchingdouble starequimatchable graphsgirthinduced matchingleafmatchingsingle starstemstrong chromatic indexstrong edge coloringstrong matchingwell-indumatchable graphs

Mathematics Subject Classification ID

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

Recommendations

• Well-indumatched Trees and Graphs of Bounded Girth
• Graphs with maximal induced matchings of the same size
• Induced matchings in subcubic graphs without short cycles
• Maximum Induced Matchings in Grids
• Induced matchings

Cites work

• Graphs with maximal induced matchings of the same size
• scientific article; zbMATH DE number 3882451 (Why is no real title available?)
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• Induced matchings
• Matching theory
• New results on induced matchings
• New results on maximum induced matchings in bipartite graphs and beyond
• NP-completeness of some generalizations of the maximum matching problem
• On the computational complexity of strong edge coloring
• Strong edge-colouring and induced matchings

Cited in

(5)

• The Komlós conjecture for graphs of girth 7
• Graphs with maximal induced matchings of the same size
• Well-indumatched Trees and Graphs of Bounded Girth
• Well-forced graphs
• Well-indumatched pseudoforests

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2172407)