Perfectly orderable graphs: A survey (Q2758336)

A linear vertex ordering of a graph \(G\) is a perfect ordering of \(G\) if for every induced subgraph \(H\) of \(G\), the greedy coloring algorithm produes an optimal coloring of \(H\). Graphs admitting a perfect ordering are called perfectly orderable. This notion introduced by Chvátal is one of the central notions within the theory of perfect graphs. It is known that recognizing perfectly orderable graphs is an NP-complete problem while a forbidden subgraph characterization of these graphs is unknown.NEWLINENEWLINENEWLINEThis survey on perfectly orderable graphs collects many results on subclasses and superclasses of perfectly orderable graphs including many results on forbidden subgraph characterizations and some complexity results for recognizing graph classes and optimizing problems. After two introductory sections, Section 7.3 collects properties of minimal nonperfectly orderable graphs; Section 7.4 gives some important edge orientation properties; Section 7.5 discusses generalizations of triangulated graphs and, in particular, describes brittle graphs and variants; Section 7.6 collects generalizations of complements of chordal bipartite graphs; Section 7.7 collects some other classes of perfectly orderable graphs, Section 7.8 discusses vertex orderings; Section 7.9 collects some generalizations of perfectly orderable graphs; and Section 7.10 deals with optimizing perfectly orderable graphs.NEWLINENEWLINENEWLINEThe reviewer adds that a recent paper by \textit{A. Brandstädt} and \textit{V. B. Le} [Split-perfect graphs: Characterizations and algorithmic use, Lect. Notes Comput. Sci. 1928, 71-82 (2000; Zbl 0989.05115)] shows that graphs having the same \(P_4\)-structure as split graphs are another subclass of perfectly orderable graphs since they are brittle graphs and contain some well-known subclasses of perfectly orderable graphs. In particular, it follows from the characterization of split-perfect graphs that a graph \(G\) is superbrittle if and only if for each of its \(p\)-connected components \(H\), the homogeneous sets of \(H\) are cographs and the characteristic graph of \(H\) is a split graph. This implies linear time recognition for superbrittle graphs.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].