Some classes of perfectly orderable graphs

In 1981, Chvátal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.