Perfect graphs

Date of Publication

1995

Document Type

Master's Thesis

Degree Name

Master of Science in Mathematics

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Severino V. Gervacio

Defense Panel Chair

Leonor A. Ruivivar

Defense Panel Member

Arlene Pascasio
Yolando Beronque

Abstract/Summary

The main objective of the study is to consolidate the works of Berge, Lovasz and Golumbic on finite perfect graphs. A graph G is perfect if G and each of its induced subgraphs have the property that the chromatic number is equal to the clique number. Specifically, it aimed to define a perfect graph, to determine if a class of graph together with its complement are perfect and to present a proof of the Perfect Graph Theorem which states that the complement of a perfect graph is perfect. The study used definitions, corollaries, lemmas and theorems necessary to accomplish its objectives. Results show that the following graphs and their complements are perfect bipartite graphs, line graph of bipartite graphs, comparability graphs, triangulated graphs, interval graphs, permutation graphs, split graphs, and threshold graphs. The Perfect Graph Theorem confirmed the perfectness of these classes of graphs. The Strong Perfect Graph Conjecture which is an open outstanding problem in graph theory was also presented.

Abstract Format

html

Language

English

Format

Print

Accession Number

TG02580

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

79 leaves

Keywords

Graph theory; Perfect graphs

This document is currently not available here.

Share

COinS