Show simple item record

Results on perfect graphs

dc.contributor.advisorHoang, Chinh
dc.contributor.authorPetrick, Mark David Timothy
dc.date.accessioned2017-06-07T20:07:59Z
dc.date.available2017-06-07T20:07:59Z
dc.date.created2000
dc.date.issued2000
dc.identifier.urihttp://knowledgecommons.lakeheadu.ca/handle/2453/3130
dc.description.abstractThe chromatic number of a graph G is the least number of colours that can be assigned to the vertices of G such that two adjacent vertices are assigned different colours. The clique number of a graph G is the size of the largest clique that is an induced subgraph of G. The notion of perfect graphs was first introduced by Claude Berge in 1960. He defined a graph G to be perfect if the chromatic number of H is equal to the clique number of H for every induced subgraph H C G. He also conjectured that perfect graphs are exactly the class of graphs with no induced odd hole (a chordless odd cycle of greater than or equal to five vertices) or no induced complement of an odd hole, an odd anti-hole. This conjecture, that still remains an open problem, is better known as the Strong Perfect Graph Conjecture (or SPGC). An equivalent statement to SPGC is that minimal imperfect graphs are odd holes and odd anti-holes. Fonlupt conjectured that all minimal imperfect graphs with a minimal cutset that is the union of more than one disjoint clique, must be an odd hole. In this thesis we prove that any hole-free graph G with a minimal cutset C that is the union of vertexdisjoint cliques must have a clique in each component o f G — C that sees all of C. We further prove that minimal imperfect graphs with a minimal cutset that is the union of two disjoint cliques have a hole. Since the introduction of perfectly orderable graphs by Chvdtal in 1984, many classes of perfectly orderable graphs and their recognition algorithms have been identified. Perfectly ordered graphs are those graphs G such that for each induced ordered subgraph H of G, the greedy (or, sequential) colouring algorithm produces an optimal colouring of H. Hohng and Reed previously studied six natural subclasses of perfecdy orderable graphs that are defined by the orientations of the P4 ’s. Four of the six classes can be recognized in polynomial time. The recognition problem for the fifth class has been proven to be NP-complete. In this thesis, we discuss the problem o f recognition for the sixth class, known as one-in-one-out graphs. Also, we consider pyramid-free graphs with the same orientation as one-in-one-out graphs and prove that this class of graphs cannot contain a directed 3-cycle of more than one equivalence class.
dc.language.isoen_US
dc.subjectGraph theory
dc.subjectPerfect graphs
dc.titleResults on perfect graphs
dc.typeThesis
etd.degree.nameMaster of Science
etd.degree.levelMaster
etd.degree.disciplineComputer Science
etd.degree.grantorLakehead University


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record