On the complexity of recognizing perfectly orderable graphs

AbstractThe question whether a polynomial time recognition algorithm for the class of perfectly orderable graphs exists was posed by Chvátal in 1981 when he introduced the notion of perfect orders. Since then several classes of perfectly orderable graphs have been identified. In this note we prove that recognizing perfectly orderable graphs is NP-complete