Induced matchings in intersection graphs.

DOI10.1016/j.disc.2003.05.001zbMath1033.05080OpenAlexW2175518075MaRDI QIDQ1427466

Publication date: 14 March 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2003.05.001

zbMATH Keywords

Asteroidal triple-free graph Cocomparability graph Induced matching Interval-filament graph Polygon-circle graph Strong chromatic index

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Unnamed Item ⋮ Graphs with maximal induced matchings of the same size ⋮ A faster algorithm for maximum independent set on interval filament graphs ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ Induced matchings in subcubic graphs without short cycles ⋮ Parameterized complexity of perfectly matched sets ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Matchings, coverings, and Castelnuovo-Mumford regularity ⋮ Maximum Induced Matchings in Grids ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Algorithms for induced biclique optimization problems ⋮ Locally searching for large induced matchings ⋮ Degenerate matchings and edge colorings ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ 3D-interval-filament graphs ⋮ Two greedy consequences for maximum induced matchings ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Approximating weighted induced matchings ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On the approximability of the maximum induced matching problem ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ The complexity of dissociation set problems in graphs ⋮ The induced separation dimension of a graph ⋮ The \(k\)-regular induced subgraph problem ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ New kernels for several problems on planar graphs ⋮ Some bounds on the maximum induced matching numbers of certain grids ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Equality of distance packing numbers ⋮ Efficient edge domination in regular graphs ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ The parameterized complexity of the induced matching problem ⋮ Maximum induced matching problem on hhd-free graphs ⋮ Algorithms on Subtree Filament Graphs ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ Recent progress on strong edge-coloring of graphs ⋮ The \(\text{v} \)-number of monomial ideals ⋮ Brambles and independent packings in chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Moderately exponential time algorithms for the maximum induced matching problem

Cites Work