Perfectly orderable graphs: A survey
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].
- Perfectly orderable graphs are quasi-parity graphs: a short proof
- New properties of perfectly orderable graphs and strongly perfect graphs
- On the complexity of recognizing a class of perfectly orderable graphs
- Quasi-brittle graphs, a new class of perfectly orderable graphs
- The story of perfectly orderable graphs
- A characterization of \(P_{4}\)-comparability graphs
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- Characterization and recognition of some opposition and coalition graph classes
- A note on strong perfectness of graphs
- On brittle graphs
- scientific article; zbMATH DE number 15158 (Why is no real title available?)
- On the perfect orderability of unions of two graphs
- New classes of perfectly orderable graphs
This page was built for publication: Perfectly orderable graphs: A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758336)
