On semi-\(P_ 4\)-sparse graphs (Q1356751)

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 properties of so-called boys in semi-\(P_4\)-sparse graphs are considered. These algorithms concern finding an optimal coloring, a largest clique and a largest stable set for a semi-\(P_4\)-sparse graph in linear time. Finally, the closure by substitution-composition of semi-\(P_4\)-sparse graphs which is the inverse operation of modular decomposition is characterized by seven forbidden configurations depicted in Section 6. Section 7 shows that for the complementary class of semi-\(P_4\)-sparse graphs a linear recognition algorithm can be obtained from a theorem analogous to Theorem 3.4 and how all previous algorithms can be applied here.