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.
For planar graphs, acyclic orientations are dual to totally cyclic orientations, orientations in which each edge belongs to a directed cycle: if is a planar graph, and orientations of are transferred to orientations of the planar dual graph of by turning each edge 90 degrees clockwise, then a totally cyclic orientation of corresponds in this way to an acyclic orientation of the dual graph and vice versa. This duality extends to nonplanar graphs as well, via the Tutte polynomial of a graph , which can be used to count both types of orientations: the number of acyclic orientations of is and the number of totally cyclic orientations is . The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial : there are different acyclic orientations. 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.
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.
- 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.
- 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.
- 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.
- Stanley, Richard P. (1973), "Acyclic orientations of graphs", Discrete Mathematics 5 (2): 171–178, doi:10.1016/0012-365X(73)90108-8.
- 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.
- 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.