Maximum induced matchings in graphs

DOI10.1016/S0012-365X(96)00125-2zbMath0877.05043OpenAlexW2025750789MaRDI QIDQ1363677

Hui Shan Zhou, Ji Ping Liu

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)

Related Items

Spanning tree enumeration and nearly triangular graph Laplacians ⋮ Counting \(r\)-graphs without forbidden configurations ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ The \(\text{v} \)-number of monomial ideals ⋮ Maximum induced matchings of random cubic graphs

Cites Work

• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Induced matchings in bipartite graphs
• On the existence of two non-neighboring subgraphs in a graph
• A bound on the chromatic number of graphs without certain induced subgraphs
• Large regular graphs with no induced \(2K_ 2\)
• Induced matchings
• Unnamed Item
• Unnamed Item
• Unnamed Item