(graph theory):

An orientation of an undirected graph is an assignment of a direction to each edge. Formally, an orientation is a function f:E->V, where E is the edge set of the graph and V is the vertex set of the graph, such that every edge is mapped to a vertex to which it is incident. This changes an undirected graph into a directed graph (a digraph).

An acyclic orientation is an orientation which has no cycles - that is, no path on the graph can end up where it started if it must follow the edge directions. The number of acyclic orientations of a graph is given by evaluating the chromatic polynomial of the graph at x = -1. [Stanley, 1978]

An example of a cyclic (i.e. not acyclic) orientation of C4 is:

    |      |
    ^      v
    |      |

Log in or register to write something here or to contact authors.