Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam (Q1814095)

The paper studies a subclass of perfectly-orderable graphs known as brittle graphs that can be recognized and given a perfect ordering in polynomial time. It points out that for a brittle graph of \(n\) vertices and \(m\) edges, an \(O(n^ 2m)\) time recognition algorithm can be derived from Chvátal's original definition, and also gives a more complicated \(O(m^ 2)\) time recognition algorithm.