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?)
- Graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Matching theory
- A characterization of well covered graphs of girth 5 or greater
- On the Complexity of General Graph Factor Problems
- Some covering concepts in graphs
- Modeling \(k\)-coteries by well-covered graphs
- Title not available (Why is that?)
- A New Algorithm for Generating All the Maximal Independent Sets
- On the completeness of a generalized matching problem
- On Eulerian and Hamiltonian Graphs and Line Graphs
- The complexity of theorem-proving procedures
- A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem
- Some results on graphs without long induced paths
- Induced matchings
- Minimal triangulations of graphs: a survey
- Well-covered claw-free graphs
- Title not available (Why is that?)
- Recognizing Greedy Structures
- Dominating sets for split and bipartite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Induced matchings in asteroidal triple-free graphs
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Split Graphs Having Dilworth Number Two
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- NP-completeness of some generalizations of the maximum matching problem
- The structure of well-covered graphs and the complexity of their recognition problems
- On well-covered triangulations. I
- 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
- New results on maximum induced matchings in bipartite graphs and beyond
- The graphs with maximum induced matching and maximum matching the same size
- Complexity results for well‐covered graphs
- Local Structure When All Maximal Independent Sets Have Equal Weight
- Title not available (Why is that?)
- On well-covered triangulations. II.
- On well-covered triangulations. III
- New results on induced matchings
- Maximum induced matchings for chordal graphs in linear time
- Greedily constructing maximal partial \(f\)-factors
- Induced matchings in intersection graphs.
- A characterization of well-covered graphs in terms of forbidden costable subgraphs
- Finding a maximum induced matching in weakly chordal graphs
- Well irredundant graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On graphs with polynomially solvable maximum-weight clique problem
- Bipartite Domination and Simultaneous Matroid Covers
- Equipackable graphs
- On distance-3 matchings and induced matchings
- Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
- Approximability results for the maximum and minimum maximal induced matching problems
- The induced matching and chain subgraph cover problems for convex bipartite 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)
