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):

Report Date:

1983-10-01

Pagination or Media Count:

18.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE