| dc.description.abstract | A graph G is perfectly orderable if it admits an order < on its vertices such that the
sequential coloring algorithm delivers an optimum coloring on each induced subgraph
(H, <) of (G, <). A graph is a threshold graph if it contains no P4 , 2K2 or C4 as
induced subgraph. A theorem of Chvatal, Hoang, Mahadev and de Werra states
that a graph is perfectly orderable if it can be written as the union of two threshold
graphs. In this thesis, we investigate possible generalizations of the above theorem.
We conjecture that if G is the union of two graphs G1 and G2 then G is perfectly
orderable whenever (i) G1 and G2 are both P4 -free and 2K2-free, or (ii) G1 is P4-free,
2K2-free and G2 is P4 -free, C4 -free. We show that the complement of the chordless
cycle with at least five vertices cannot be a counter-example to our conjecture and
we prove, jointly with Hoang, a special case of (i): if G1 and G2 are two edge disjoint
graphs that are P4 -free and 2K2 -free then the union of G1 and G2 is perfectly
orderable. | |
