Graphs with maximal induced matchings of the same size
DOI10.1016/J.DAM.2016.08.015zbMATH Open1350.05129OpenAlexW2521882261WikidataQ57633759 ScholiaQ57633759MaRDI QIDQ344824FDOQ344824
Authors: Philippe Baptiste, M. Y. Kovalyov, Yury L. Orlovich, Frank Werner, I.È. Zverovich 
Publication date: 24 November 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.08.015
Recommendations
- A characterization of well-indumatchable graphs having girth greater than seven
- Well-indumatched Trees and Graphs of Bounded Girth
- The structure of well-covered graphs and the complexity of their recognition problems
- Independent domination and matchings in 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
computational complexityinduced matchingwell-covered graphoptimization problemforbidden induced subgraph
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A New Algorithm for Generating All the Maximal Independent Sets
- A characterization of well covered graphs of girth 5 or greater
- A characterization of well-covered graphs in terms of forbidden costable subgraphs
- A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem
- Approximability results for the maximum and minimum maximal induced matching problems
- Bipartite Domination and Simultaneous Matroid Covers
- Complexity results for well‐covered graphs
- Computing the Minimum Fill-In is NP-Complete
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- Dominating sets for split and bipartite graphs
- Equipackable graphs
- Finding a maximum induced matching in weakly chordal 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
- Graph theory
- Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
- Greedily constructing maximal partial \(f\)-factors
- Induced matchings
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection graphs.
- Local Structure When All Maximal Independent Sets Have Equal Weight
- Matching theory
- Maximum induced matchings for chordal graphs in linear time
- Minimal triangulations of graphs: a survey
- Modeling \(k\)-coteries by well-covered graphs
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- New results on maximum induced matchings in bipartite graphs and beyond
- On Eulerian and Hamiltonian Graphs and Line Graphs
- On distance-3 matchings and induced matchings
- On graphs with polynomially solvable maximum-weight clique problem
- On the Complexity of General Graph Factor Problems
- On the completeness of a generalized matching problem
- On well-covered triangulations. I
- On well-covered triangulations. II.
- On well-covered triangulations. III
- Recognizing Greedy Structures
- Some covering concepts in graphs
- Some results on graphs without long induced paths
- Split Graphs Having Dilworth Number Two
- The complexity of theorem-proving procedures
- The graphs with maximum induced matching and maximum matching the same size
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- The structure of well-covered graphs and the complexity of their recognition problems
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Well irredundant graphs
- Well-covered claw-free graphs
Cited In (7)
- Maximum induced matching problem on hhd-free graphs
- On graphs with induced matching number almost equal to matching number
- Maximal matchings in graphs with large neighborhoods of independent vertices
- Well-indumatched pseudoforests
- Maximum induced matchings in graphs
- Well-indumatched Trees and Graphs of Bounded Girth
- A characterization of well-indumatchable graphs having girth greater than seven
This page was built for publication: Graphs with maximal induced matchings of the same size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344824)
