Linear recognition of pseudo-split graphs (Q1331889)

Simple graphs with a vertex set which can be partitioned into a clique and a stable set are called split graphs. These graphs were introduced by Hammer and Földes, who also proved that \(G\) is a split graph iff it contains no induced \(C_ 4\), \(C_ 5\) or \(2K_ 2\). \((C_ k\) denotes a chordless cycle on \(k\) vertices, and \(2K_ 2\) is the graph formed by two cliques of size two.) Further, such graphs can be characterized by using the ordered degree sequence of the vertices. The recognition algorithm is a linear-time one. The authors introduce a generalization of split graphs. They call a graph pseudo-split graph if it contains no induced \(C_ 4\) or \(2K_ 2\), and consequently a pseudo-split graph that has an induced \(C_ 5\) is called imperfect. In Theorem 2 it is proved that a pseudo-split graph is either an imperfect pseudo-split graph or a split graph. And as for split graphs the authors give an analogous characterization of imperfect pseudo-split graphs using the degree sequence (see Theorem 3). Applying this result they describe a linear-time recognition algorithm for imperfect pseudo- split graphs (with given ordered degree sequence). Finally, a further generalization is given by a \(H\)-split graph which is an imperfect pseudo-split graph that has instead of an induced \(C_ 5\) an induced subgraph isomorphic to a fixed graph \(H\). A graph \(G\) is called an \({\mathfrak H}\)-split graph if it is \(H\)-split for some element \(H\) of a class \({\mathfrak H}\) of graphs. A necessary and sufficient condition for being an \({\mathfrak H}\)-split graph is given in Theorem 4. This theorem also yields a linear-time recognition algorithm for a certain fixed degree sequence.