A min-max property of chordal bipartite graphs with applications

DOI10.1007/s00373-010-0922-0zbMath1219.05136MaRDI QIDQ1959718

Arthur H. Busch, R. Sritharan, Atif A. Abueida

Publication date: 7 October 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-010-0922-0

zbMATH Keywords

bipartite graphs; induced matching; chain cover

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Matchings, coverings, and Castelnuovo-Mumford regularity, A constant factor approximation algorithm for boxicity of circular arc graphs, Maximum induced matching problem on hhd-free graphs, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Maximum induced matchings for chordal graphs in linear time
• On the complexity of posets
• Induced matchings
• On the complexity of the k-chain subgraph cover problem
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Short proofs for interval digraphs
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Finding a maximum induced matching in weakly chordal graphs
• Optimizing weakly triangulated graphs
• New results on induced matchings
• Threshold Dimension of Graphs
• Circular‐arc digraphs: A characterization
• Graph Classes: A Survey
• On the 2-Chain Subgraph Cover and Related Problems
• Interval bigraphs and circular arc graphs
• Partially Ordered Sets