Compositions for Perfect Graphs.
Management science research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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.
- Theoretical Mathematics