Tournament-like oriented graphs
Pavol Hell, Jing Huang · 1992
A local tournament is an oriented graph in which the inset as well as the outset of each vertex induces a tournament. Local tournaments possess many properties of tournaments and have interesting structure. In 1982, Skrien proved (in different terminology), using a deep structural characterization of proper circular arc graphs by Tucker, that a connected graph is local-tournament-orientable if and only if it is a proper circular arc graph. In Chapter 2, we shall give a simple O($m\Delta$) algorithm to decide if a graph can be oriented as a local tournament, and hence whether or not it is a proper circular arc graph. We analyze relationships among local tournaments, local transitive tournaments, and proper circular arc graphs. We obtain theorems to describe all possible local-tournament orientations of a proper circular arc graph. In Chapter 3, we shall present an O($m\Delta$) algorithm to recognize comparability graphs and to calculate transitive orientations. Our method can be applied to recognize proper circular arc graphs and to find local-transitive-tournament orientations, and can also be applied to recognize proper interval graphs and to find acyclic local-tournament orientations. We shall give a simple proof of Skrien's theorem, which does not depend on Tucker's result. In Chapter 4, we shall present two O(m + n) time algorithms. One is for recognizing proper interval graphs and for finding an associated interval family. The other is for recognizing proper circular arc graphs and for finding an associated circular arc family. In Chapter 5, we shall obtain two additional O(m + n) time algorithms for proper circular arc graphs by using the auxiliary local-tournament orientations. One is for finding maximum cliques, and the other is for determining c-colourability. In Chapter 6, we shall introduce a new class of oriented graphs, namely, in-tournaments, which contains the class of local tournaments. We shall show that some of the basic and very nice properties of tournaments extend not only to local tournaments, but also to this more general class of digraphs. Our results imply a polynomial time algorithm for finding hamiltonian paths and cycles in the class of in-tournaments. We shall also investigate the class of graphs which are orientable as in-tournaments. Finally, in Chapter 7, we shall introduce another class of oriented graphs, i.e., those of Moon type. We shall find a close relationship between the class of oriented graphs of Moon type and the class of local tournaments. In fact, oriented graphs of Moon type can be characterized in terms of local transitive tournaments.