Acyclic orientation

In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint.

The Gallai–Hasse–Roy–Vitaver theorem states that a graph has an acyclic orientation in which the longest path has k vertices if and only if it can be colored with k colors.[1]

For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: if G is a planar graph, and orientations of G are transferred to orientations of the planar dual graph of G by turning each edge 90 degrees clockwise, then a totally cyclic orientation of G corresponds in this way to an acyclic orientation of the dual graph and vice versa.[2] This duality extends to nonplanar graphs as well, via the Tutte polynomial T_G of a graph G, which can be used to count both types of orientations: the number of acyclic orientations of G is T_G(2,0) and the number of totally cyclic orientations is T_G(0,2).[3] The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial \chi_G: there are |\chi_G(-1)| different acyclic orientations.[4] The set of all acyclic orientations of a given graph may be given the structure of a partial cube, in which two acyclic orientations are adjacent whenever they differ in the direction of a single edge.[5]

An acyclic orientation of a complete graph is called a transitive tournament, and is equivalent to a total ordering of the graph's vertices. In such an orientation there is in particular exactly one source and exactly one sink; more generally, an acyclic orientation with a unique source and a unique sink is called a bipolar orientation.[6]

References

  1. ↑ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
  2. ↑ Welsh, Dominic (1997), "Approximate counting", Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser. 241, Cambridge: Cambridge Univ. Press, pp. 287–323, doi:10.1017/CBO9780511662119.010, MR 1477750.
  3. ↑ Las Vergnas, Michel (1980), "Convexity in oriented matroids", Journal of Combinatorial Theory, Series B 29 (2): 231–243, doi:10.1016/0095-8956(80)90082-9, MR 586435.
  4. ↑ Stanley, Richard P. (1973), "Acyclic orientations of graphs", Discrete Mathematics 5 (2): 171–178, doi:10.1016/0012-365X(73)90108-8.
  5. ↑ Fukuda, Komei; Prodon, Alain; Sakuma, Tadashi (2001), "Notes on acyclic orientations and the shelling lemma", Theoretical Computer Science 263 (1-2): 9–16, doi:10.1016/S0304-3975(00)00226-7, MR 1846912.
  6. ↑ de Fraysseix, Hubert; de Mendez, Patrice Ossona; Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics 56 (2-3): 157–179, doi:10.1016/0166-218X(94)00085-R, MR 1318743.