On semi-\(P_ 4\)-sparse graphs
type: Item
instance of: scholarly article
title: On semi-\(P_ 4\)-sparse graphs
zbMATH Open document ID: 0873.05071
DOI: 10.1016/S0012-365X(96)00177-X
author: Jean-Luc Fouquet
author: Vassilis Giakoumakis
published in: Discrete Mathematics
publication date: 1997-10-26T00:00:00Z
review text: Let \(G=(V,E)\) be a finite simple graph. \(G\) is said to be \(P_4\)-sparse if any set of five vertices of \(G\) contains at the most one induced chordless path \(P_4\). These graphs belong to the class of perfect graphs. In the present paper, the authors consider semi-\(P_4\)-sparse graphs which form an overclass of the \(P_4\)-sparse graphs, but which is not a class of perfect graphs. \(G\) is a semi-\(P_4\)-sparse graph if \(G\) does not contain as induced subgraph a \(P_5\), \(\overline P_5\) or a kite which is the complement of a tree of order five with three pendent vertices (this graph is denoted a fork). To find a linear recognition algorithm for semi-\(P_4\)-sparse graphs the modular decomposition is used which is a form of decomposition of \(G\) that associates with \(G\) a certain unique decomposition tree and therefore in Section 2 its fundamental properties are considered and additional concepts are introduced; for instance, the prime or indecomposable graphs which have only trivial modules \(M\) (a set of vertices \(M\) of \(G\) is said to be a module if every vertex outside \(M\) is either adjacent to all vertices of \(M\) or to none of them). In Section 3 the main result (Theorem 3.4) is given which characterizes the semi-\(P_4\)-sparse graphs: Let \(G\) be a prime semi-\(P_4\)-sparse graph. Then at least one of the following statements is true: (i) \(G\) is bipartite, (ii) \(G\) is isomorphic to a chordless cycle \(C_5\), (iii) \(G\) is isomorphic to a starfish or to an urchin (these graphs are depicted in Fig. 4). This theorem is the cornerstone of the linear recognition algorithm which is presented in Section 4. Its time complexity is \({\mathcal O}(n+m)\) with the cardinalities \(n=|V(G)|\) and \(m=|E(G)|\). Section 5 shows that known linear algorithms (Chvátal et al.) for perfect graphs that are \(P_5\), \(\overline P_5\) and \(C_5\)-free can be extended to the class of semi-\(P_4\)-sparse graphs (which may contain a \(C_5\)). Therefore the pro…
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1019102
zbMATH Keywords: semi-\(P_ 4\)-sparse graphs
zbMATH Keywords: linear recognition algorithm
zbMATH Keywords: modular decomposition
zbMATH Keywords: indecomposable graphs
zbMATH Keywords: coloring
zbMATH Keywords: clique
zbMATH Keywords: stable set
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q4773298
cites work: Graphs with unique maximal clumpings
cites work: Q3899969
cites work: A Fast Algorithm for the Decomposition of Graphs and Posets
cites work: Four classes of perfectly orderable graphs
cites work: Q4954442
cites work: Clustering and domination in perfect graphs
cites work: Complement reducible graphs
cites work: Q3676177
cites work: A Linear Recognition Algorithm for Cographs
cites work: On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
cites work: Transitiv orientierbare Graphen
cites work: Q3836509
cites work: The complexity of comparability graph recognition and coloring
cites work: Q3328583
cites work: Two-Processor Scheduling with Start-Times and Deadlines
cites work: Q3216686
cites work: Weakly triangulated graphs
cites work: Q5598258
cites work: A tree representation for \(P_ 4\)-sparse graphs
cites work: Recognizing $P_4 $-Sparse Graphs in Linear Time
cites work: Q3355252
cites work: Q3686754
cites work: Q3683903
cites work: Incremental modular decomposition
cites work: On the closure of triangle-free graphs under substitution
cites work: Graph derivatives
cites work: On a property of the class of n-colorable graphs
cites work: \(P_ 4\)-trees and substitution decomposition
full work available at URL: s0012-365x(96)00177-x
OpenAlex ID: W2576553421
description: scientific article; zbMATH DE number 1019102