A translation of Gallai's paper: `Transitiv orientierbare Graphen' (Q2758332)

This is a very faithful, but not always verbatim, translation, with modernized notation, of Tibor Gallai's fundamental paper on transitively orientable (or comparability) graphs [Acta Math. Acad. Sci. Hung. 18, 25-66 (1967; Zbl 0153.26002)]. Gallai provided a characterization of transitively orientable graphs given by the list of all minimal nontransitively orientable graphs, as well as important structural results valid for all graphs. He proved that a graph is transitively orientable if and only if an auxiliary graph is bipartite, and he described a procedure (which is seen to be polynomial-time) for constructing this auxiliary graph. The only non-trivial step is the computation of the connected components of the neighborhood of a vertex. Thus Gallai explicitly described an algorithm for testing graphs for transitive orientability. The translators provide a brief forward, in which they cite relevant literature.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].