Chvataf defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P4 or not an endpoint of any P4. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an 0(n4) algorithm to recognize HHD-free graphs, and also an 0(n4) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in 0(n4) time.
1. Introduction
An order < on the vertices of a graph G is perfect if the ordered graph (G, <) contains no induced subgraph F with four vertices a , b, c , d and three edges ab, bc, cd, and the relations a < b, d < c (F is called an obstruction). Chvfital [ 3 ] proved that if a graph G admits a perfect order <, then an optimal coloring of G can be obtained by applying the following simple and natural algorithm:
(i) scan the vertices of G in the order <, and (ii) assign to each vertex v, the smallest positive integer assigned to no neighbor v, of v, with j < i.
Chvfital showed that the above algorithm, applied to (G, <), uses only w(G) colors, with w ( G ) standing for clique number of G (i.e., the number of vertices in a largest clique of G). This implies that perfectly orderable graphs (i.e., graphs that admit a perfect order) are perfect in the sense of Berge [2]: a graph G is perfect if for each induced subgraph H of G , the chromatic number of H