Four classes of perfectly orderable graphs

Abstract

Abstract A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F , a certain “greedy” coloring heuristic delivers an optimal coloring of F . No polynomial‐time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.