Basic perfect graphs and their extensions Original Research Article

In this article, we present a characterization of basic graphs in terms of forbidden induced subgraphs. This class of graphs was introduced by Conforti et al. (Square-free perfect graphs, J. Combin. Theory Ser. B, 90 (2) (2004) 257–307), and it plays an essential role in the announced proof of the Strong Perfect Graph Conjecture by Chudnovsky et al. (). Let G and H be graphs. A substitution of H in G replacing a vertex image is the graph image consisting of disjoint union of H and image with the additional edge-set image. For a class of graphs image, its substitutional closure image consists of all graphs that can be obtained from graphs of image by repeated substitutions. We apply the reducing pseudopath method (Discrete Appl. Math. 128 (2–3) (2003) 487–509) to characterize the substitutional closure of the class of basic graphs in terms of forbidden induced subgraphs.