Graphs with maximal induced matchings of the same size
DOI10.1016/j.dam.2016.08.015zbMath1350.05129OpenAlexW2521882261WikidataQ57633759 ScholiaQ57633759MaRDI QIDQ344824
Yury L. Orlovich, Mikhail Y. Kovalyov, Frank Werner, Philippe Baptiste, Igor Edm. 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
computational complexityoptimization probleminduced matchingwell-covered graphforbidden induced subgraph
Extremal problems in graph theory (05C35) 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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem
- On distance-3 matchings and induced matchings
- Dominating sets for split and bipartite graphs
- Minimal triangulations of graphs: a survey
- Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
- Approximability results for the maximum and minimum maximal induced matching problems
- On well-covered triangulations. II.
- On well-covered triangulations. III
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- Maximum induced matchings for chordal graphs in linear time
- Greedily constructing maximal partial \(f\)-factors
- Some results on graphs without long induced paths
- Matching theory
- NP-completeness of some generalizations of the maximum matching problem
- A characterization of well covered graphs of girth 5 or greater
- Induced matchings
- The structure of well-covered graphs and the complexity of their recognition problems
- Induced matchings in asteroidal triple-free graphs
- On well-covered triangulations. I
- Induced matchings in intersection graphs.
- A characterization of well-covered graphs in terms of forbidden costable subgraphs
- 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
- Finding a maximum induced matching in weakly chordal graphs
- Well irredundant graphs
- Well-covered claw-free graphs
- New results on maximum induced matchings in bipartite graphs and beyond
- New results on induced matchings
- The graphs with maximum induced matching and maximum matching the same size
- ModelingK-coteries by well-covered graphs
- On the Complexity of General Graph Factor Problems
- On graphs with polynomially solvable maximum-weight clique problem
- Computing the Minimum Fill-In is NP-Complete
- Complexity results for well‐covered graphs
- Split Graphs Having Dilworth Number Two
- A New Algorithm for Generating All the Maximal Independent Sets
- Local Structure When All Maximal Independent Sets Have Equal Weight
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Bipartite Domination and Simultaneous Matroid Covers
- Recognizing Greedy Structures
- On the completeness of a generalized matching problem
- On Eulerian and Hamiltonian Graphs and Line Graphs
- Some covering concepts in graphs
- The complexity of theorem-proving procedures
This page was built for publication: Graphs with maximal induced matchings of the same size
