Maximum induced matchings in graphs

DOI10.1016/S0012-365X(96)00125-2MaRDI QIDQ1363677zbMATH OpenOpenAlexFDO

Authors Jiping Liu, Huishan Zhou

Publication date 10 August 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00125-2

zbMATH Keywords

maximum induced matchingconnected bipartite graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Induced matchings in graphs of bounded maximum degree
• On maximum induced matchings in bipartite graphs
• Graphs with maximal induced matchings of the same size
• The graphs with maximum induced matching and maximum matching the same size
• Maximum Induced Matchings in Grids
• Maximum induced matchings close to maximum matchings
• The Maximum Number of Dominating Induced Matchings
• Combinatorial Geometry and Graph Theory

Cites work

• scientific article; zbMATH DE number 425392 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• A bound on the chromatic number of graphs without certain induced subgraphs
• Graph theory
• Induced matchings
• Induced matchings in bipartite graphs
• Large regular graphs with no induced \(2K_ 2\)
• On the existence of two non-neighboring subgraphs in a graph
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree

Cited in

(19)

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Second kind maximum matching graph
• Exact Solution Algorithms for the Chordless Cycle Problem
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Maximum induced matchings of random cubic graphs
• Maximum induced matching problem on hhd-free graphs
• Finding a maximum matching in a permutation graph
• Basic maximal \(2K_2\)-free graphs
• Maximum Induced Matchings in Grids
• scientific article; zbMATH DE number 4114698 (Why is no real title available?)
• The Maximum Number of Dominating Induced Matchings
• Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs
• Counting \(r\)-graphs without forbidden configurations
• Maximal matchings in graphs with large neighborhoods of independent vertices
• Approximability results for the maximum and minimum maximal induced matching problems
• Maximum induced matchings for chordal graphs in linear time
• The \(\text{v} \)-number of monomial ideals
• Spanning tree enumeration and nearly triangular graph Laplacians
• Maximum induced matchings close to maximum matchings

This page was built for publication: Maximum induced matchings in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363677)