Perfect graphs

• Main Author: Lim, Yvette F.
• Format: text
• Language: English
• Published: Animo Repository 1995
• Subjects: Graph theory; Perfect graphs; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1780
• Institution: De La Salle University

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.