Compositions for perfect graphs (Q2266722): Difference between revisions

From MaRDI portal
Created claim: Wikidata QID (P12): Q56430120, #quickstatements; #temporary_batch_1703769339033
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 10:27, 2 February 2024

scientific article
Language Label Description Also known as
English
Compositions for perfect graphs
scientific article

    Statements

    Compositions for perfect graphs (English)
    0 references
    1985
    0 references
    In this paper we introduce a new graph composition, called 2-amalgam, and we prove that the 2-amalgam of perfect graphs is perfect. This composition generalizes many of the operations known to preserve perfection, such as the clique identification, substitution, join and amalgam operations. We give polynomial-time algorithms to determine whether a general graph is decomposable with respect to the 2-amalgam or amalgam operations.
    0 references
    perfect graphs
    0 references
    graph decomposition
    0 references
    graph composition
    0 references
    2-amalgam
    0 references
    algorithms
    0 references

    Identifiers