| dc.description.abstract | The 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. | |
