# 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 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.^{[2]} 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 .^{[3]} The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial : there are 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

- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.