Algorithms for unipolar and generalized split graphs

A graph G=(V,E) is a unipolar graph if there exists a partition V=V1∪V2 such that V1 is a clique and V2 induces the disjoint union of cliques. The complement-closed class of generalized split graphs contains those graphs G such that either Gor the complement of G is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all C5-free (and hence, almost all perfect graphs) are generalized split graphs. In this paper, we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time O(nm+nmF), where mF is the number of edges added in a minimal triangulation of the given graph. Generalized split graphs can be recognized via this algorithm in O(n3) time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in O(n+m) time, and for finding a maximum clique and a minimum proper coloring in O(n2.5/logn) time, when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bounds. We also report that the perfect code problem is NP-complete for chordal unipolar graphs.