The graphs with maximum induced matching and maximum matching the same size
From MaRDI portal
Publication:2568473
DOI10.1016/j.disc.2004.07.022zbMath1073.05054OpenAlexW1979477295MaRDI QIDQ2568473
Publication date: 10 October 2005
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2004.07.022
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (32)
Acyclic matchings in graphs of bounded maximum degree ⋮ A new view toward vertex decomposable graphs ⋮ On graphs with induced matching number almost equal to matching number ⋮ Graphs with maximal induced matchings of the same size ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ On the Castelnuovo-Mumford regularity of squarefree powers of edge ideals ⋮ The regularity and h-polynomial of Cameron-Walker graphs ⋮ Gorenstein and Cohen–Macaulay matching complexes ⋮ Regularity of powers of edge ideals: from local properties to global bounds ⋮ Degenerate matchings and edge colorings ⋮ Regularity of symbolic powers of edge ideals of Cameron-Walker graphs ⋮ Algebraic study on Cameron-Walker graphs ⋮ An upper bound for the regularity of symbolic powers of edge ideals of chordal graphs ⋮ Approximating weighted induced matchings ⋮ Upper bounds for the regularity of powers of edge ideals of graphs ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ The complexity of dissociation set problems in graphs ⋮ Coverings, Matchings and the number of maximal independent sets of graphs ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ Regularity and \(a\)-invariant of Cameron-Walker graphs ⋮ Dominating induced matchings of finite graphs and regularity of edge ideals ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Equality of distance packing numbers ⋮ Maximal independent sets and regularity of graphs ⋮ Matching numbers and dimension of edge ideals ⋮ Regularity, matchings and Cameron-Walker graphs ⋮ Symbolic powers of vertex cover ideals ⋮ Brambles and independent packings in chordal graphs ⋮ Homological invariants of Cameron–Walker Graphs ⋮ Independent packings in structured graphs ⋮ Maximum induced matchings close to maximum matchings ⋮ Upper bounds for the regularity of symbolic powers of certain classes of edge ideals
Cites Work
- Unnamed Item
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Irredundancy in circular arc graphs
- NP-completeness of some generalizations of the maximum matching problem
- Comparability graphs and intersection graphs
- Thresholds for classes of intersection graphs
- Induced matchings
- Covering and coloring polygon-circle graphs
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection 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
- Finding a maximum induced matching in weakly chordal graphs
- New results on induced matchings
- TWO THEOREMS IN GRAPH THEORY
- Bipartite Domination and Simultaneous Matroid Covers
This page was built for publication: The graphs with maximum induced matching and maximum matching the same size
