On semi-P4-sparse graphs Original Research Article

In this paper, we define a graph G as semi-P4-sparse if G does not contain as induced subgraph a P5, a P5 or the complement of a fork, where a fork is the tree of order 5 with 3 pendent vertices. This new class of graphs contains strictly the class of P4-sparse graphs. Using modular decomposition we first propose a linear recognition algorithm for semi-P4-sparse graphs and next, we show that with very little work, we can extend the linear algorithms of Chvátal et al. (1987) concerning the class of perfect graphs that are P5, P5 and C5-free, for finding an optimal coloring, a largest clique and a largest stable set of a semi-P4-sparse graph G. Finally, we characterize by forbidden configurations the closure by substitution-composition (the inverse operation of modular decomposition) of semi-P4-sparse graphs, composition operation of graphs that (among other properties) preserves perfection.