On the complexity of recognizing a class of perfectly orderable graphs

AbstractRecently Middendorf and Pfeiffer proved that recognizing perfectly orderable graphs is NP-complete. Hoàng and Reed had previously studied six natural subclasses of perfectly orderable graphs that are defined by the orientations of the P4's. Four of the six classes can be recognized in polynomial time. We show in this paper that it is NP-complete to recognize the fifth class