Restricted Bipartite Graphs: Comparison and Hardness Results

摘要

Convex bipartite graphs are a subclass of circular convex bipartite graphs and chordal bipartite graphs. Chordal bipartite graphs are a subclass of perfect elimination bipartite graphs and tree convex bipartite graphs. No other inclusion among them is known. In this paper, we make a thorough comparison on them by showing the nonemptyness of each region in their Venn diagram. Thus no further inclusion among them is possible, and the known complexity results on them are incomparable. We also show the NP-completeness of treewidth and feedback vertex set for perfect elimination bipartite graphs.