Decomposition of perfect graphs (Q1072566): Difference between revisions

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.