Linear recognition of pseudo-split graphs
type: Item
instance of: scholarly article
title: Linear recognition of pseudo-split graphs
zbMATH Open document ID: 0805.05069
DOI: 10.1016/0166-218X(94)00022-0
author: Frédéric Maffray
author: Myriam Preissmann
published in: Discrete Applied Mathematics
publication date: 1995-01-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 626247
zbMATH Keywords: degree sequence
zbMATH Keywords: recognition algorithm
zbMATH Keywords: split graphs
zbMATH Keywords: pseudo-split graph
zbMATH Keywords: characterization
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q4773298
cites work: Graphs with no induced \(C_ 4\) and \(2K_ 2\)
cites work: Q4193514
cites work: Q3328583
cites work: The splittance of a graph
cites work: \(\beta\)-perfect graphs
description: scientific article; zbMATH DE number 626247