# 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 ${\displaystyle G}$ is a planar graph, and orientations of ${\displaystyle G}$ are transferred to orientations of the planar dual graph of ${\displaystyle G}$ by turning each edge 90 degrees clockwise, then a totally cyclic orientation of ${\displaystyle 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 ${\displaystyle T_{G}}$ of a graph ${\displaystyle G}$, which can be used to count both types of orientations: the number of acyclic orientations of ${\displaystyle G}$ is ${\displaystyle T_{G}(2,0)}$ and the number of totally cyclic orientations is ${\displaystyle T_{G}(0,2)}$.[3] The number of acyclic orientations may also be counted using a different polynomial, the chromatic polynomial ${\displaystyle \chi _{G}}$: there are ${\displaystyle |\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. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
2. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
3. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
4. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
5. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
6. {{#invoke:citation/CS1|citation |CitationClass=citation }}.