On variations of \(P_{4}\)-sparse graphs
type: Item
instance of: scholarly article
title: On variations of \(P_{4}\)-sparse graphs
zbMATH Open document ID: 1022.05069
DOI: 10.1016/S0166-218X(03)00180-X
author: Andreas Brandstädt
author: Raffaele Mosca
published in: Discrete Applied Mathematics
publication date: 2003-09-09T00:00:00Z
review text: A graph is \(P_4\)-sparse if every subgraph induced by five vertices contains at most one \(P_4\). Hoàng, who introduced this class, characterised \(P_4\)-sparse graphs by their prime graphs under modular decomposition. A \(P_4\)-extension is a graph on five vertices containing a \(P_4\). \(P_4\)-sparse graphs and several superclasses defined by forbidden \(P_4\)-extensions have bounded clique-width. This allows linear-time algorithms for all problems expressible in LinEMSOL(\(\tau_{1,\text{ L}}\)) when restricted to such a class, see \textit{B. Courcelle, J. A. Makowsky} and \textit{U. Rotics} [Theory Comput. Syst. 33, 125-150 (2000; Zbl 1009.68102)]. The authors classify all superclasses of \(P_4\)-sparse graphs defined by forbidding one \(P_4\)-extension into classes of bounded clique-width and classes of unbounded clique-width. A similar classification of classes defined by up to three forbidden \(P_4\)-extensions was given in a related paper additionally authored by \textit{F. F. Dragan} and \textit{H.-O. Le} [Lect. Notes Comput. Sci. 2573, 57-67 (2002; Zbl 1022.68090)].
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1977916
zbMATH Keywords: \(P_4\)-spares graph
zbMATH Keywords: prime graph
zbMATH Keywords: clique-width
zbMATH Keywords: linear time algorithm
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: \(P_4\)-extension
MaRDI profile type: Publication
cites work: On the \(p\)-connectedness of graphs---a survey
cites work: A nice class for the vertex packing problem
cites work: Stability number of bull- and chair-free graphs revisited
cites work: Graph Classes: A Survey
cites work: Complement reducible graphs
cites work: Q3676177
cites work: A Linear Recognition Algorithm for Cographs
cites work: Handle-rewriting hypergraph grammars
cites work: Q4232773
cites work: Upper bounds to the clique width of graphs
cites work: Q4954442
cites work: Efficient and practical algorithms for sequential modular decomposition
cites work: Q4193514
cites work: Q3836509
cites work: On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
cites work: Difference graphs
cites work: Some classes of perfectly orderable graphs
cites work: Recognizing $P_4 $-Sparse Graphs in Linear Time
cites work: A tree representation for \(P_ 4\)-sparse graphs
cites work: Linear time optimization algorithms for \(P_ 4\)-sparse graphs
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: Modular decomposition and transitive orientation
cites work: The Complexity of the Partial Order Dimension Problem
description: scientific article; zbMATH DE number 1977916