Split-Perfect Graphs: Characterizations and Algorithmic Use
Andreas Brandstädt, Van Bang Lê · SIAM Journal on Discrete Mathematics · 2004
Two graphs G and H with the same vertex set Vare P 4 -isomorphic if every four vertices {a,b,c,d} \subseteq V$ induce a chordless path (denoted by P 4 ) in G if and only if they induce a P 4 in H. We call a graph split-perfect if it is P 4 -isomorphic to a split graph (i.e., a graph being partitionable into a clique and a stable set). This paper characterizes the new class of split-perfect graphs using the concepts of homogeneous sets and p-connected graphs and leads to a linear time recognition algorithm for split-perfect graphs, as well as efficient algorithms for classical optimization problems on split-perfect graphs based on the primeval decomposition of graphs. The optimization results considerably extend previous ones on smaller classes such as P 4 --sparse graphs, P 4 -lite graphs, P 4 --laden graphs, and (7,3)-graphs. Moreover, split-perfect graphs form a new subclass of brittle graphs containing the superbrittle graphs for which a new characterization is obtained leading to linear time recognition.