It is not known whether perfect graphs can be recognized in polynomial time. One attempt is to use some graph decomposition to decompose a given graph into irreducible components, i.e., components which cannot be decomposed. Perfect graphs can be recognized in polynomial time if: (1) the composition (reverse operation of the decomposition) preserves perfection; (2) reducible graphs can be decomposed in polynomial time into two smaller graphs one of which is irreducible, and (3) irreducible perfect graphs can be recognized in polynomial time. In this paper we introduce a new composition of graphs for which (1) and (2) hold. This composition generalizes clique identification, the join and the amalgam operations and, together with complementation, it encompasses all the operations preserving perfection known to us.
展开▼
