Maximum-Size Subgraphs of P4-Sparse Graphs Admitting a Perfect Matching

Abstract. In this paper, we address the problem of computing a maximum-size subgraph of a P4-sparse graph which admits a perfect matching; in the case where the graph has a perfect matching, the solution to the problem is the entire graph. We establish a characterization of such subgraphs, and describe an algorithm for the problem which for a P4-sparse graph on n vertices and m edges, runs in O(n + m) timeand space. The above results also hold for the class of complement reducible graphs or cographs, a well-known subclass of P4-sparse graphs. Keywords: Perfect graphs, P4-sparse graphs, cographs, maximum-size subgraphs, maximum matchings, perfect matching