Accession Number : ADA137611

Title :   Compositions for Perfect Graphs.

Descriptive Note : Management science research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Cornuejols,G ; Cunningham,W H

PDF Url : ADA137611

Report Date : Oct 1983

Pagination or Media Count : 18

Abstract : 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.

Descriptors :   *Graphs, *Decomposition, Numerical methods and procedures, Algorithms, Computations

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE