Decomposition of perfect graphs (Q1072566)

In this paper we describe general composition and decomposition schemes for perfect graphs, which covers almost all recent results in this area, e.g. the amalgam and the 2-amalgam split. Our approach is based on the consideration of induced cycles and their complements in perfect graphs (as opposed to the consideration of cycles for defining biconnected or 3-connected graphs). Our notion of 1-inseparable graphs is ``parallel'' to that of biconnected graphs in that different edges in different inseparable components are not contained in any induced cycle or any complement of an induced cycle. Furthermore, in a special case which generalizes the join operation, this definition is self-complementary in a natural fashion. Our 2-composition operation, which only creates even induced cycles in the composed graphs, is based on two perfection-preserving merge operations on perfect graphs. As a by-product, we present some new properties of minimally imperfect graphs.