On brittle graphs
Chı́nh T. Hoàng, N. Khouzam · Journal of Graph Theory · 1988
Abstract Chvátal 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 O(n4) algorithm to recognize HHD‐free graphs, and also an O(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 O(n4) time.