Recognizing brittle graphs: remarks on a paper of Hoàng and Khouzam

AbstractA graph is perfect if the size of the maximum clique equals the chromatic number in every induced subgraph. Chvátal defined a subclass of perfect graphs known as perfectly-orderable graphs, which have the property that a special ordering on the vertices leads to a trivial algorithm to find an optimum coloring. He also identified a subclass of the perfectly-orderable graphs, which he called brittle graphs, characterized by the property that every nonempty induced subgraph contains a vertex x such that x is either not an endpoint of a P4 or is not in the middle of a P4. The brittle graphs were studied in a recent paper of Hoàng and Khouzam [J. Graph Theory 12 (1988) 391-404] where the authors gave alternate characterizations one of which leads to an O(n3m) time recognition algorithm for brittle graphs, where n is the number of vertices and m is the number of edges. In contrast, no polynomial-time recognition algorithms are known for either perfect graphs or perfectly-orderable graphs. We point out that an O(n2m) time recognition algorithm for brittle graphs can be derived from Chvátal's definition, and we present a more complicated O(m2) time recognition algorithm