Decomposition of perfect graphs (Q1072566)

From MaRDI portal
Revision as of 12:09, 17 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Decomposition of perfect graphs
scientific article

    Statements

    Decomposition of perfect graphs (English)
    0 references
    0 references
    1987
    0 references
    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.
    0 references
    perfect graphs
    0 references
    2-amalgam split
    0 references
    induced cycles
    0 references
    2-composition operation
    0 references
    graph colouring
    0 references
    graph composition
    0 references
    graph decomposition
    0 references

    Identifiers