On brittle graphs |
| |
Authors: | C T Hong N Khouzam |
| |
Institution: | C. T. Hoàng,N. Khouzam |
| |
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. |
| |
Keywords: | |
|
|