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, and C4 as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G1 and G2, then G is perfectly orderable whenever G1 and G2 are both P4‐free and 2K2‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: 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. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000 |