# Questions tagged [acyclic-orientations]

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.

3
questions

**0**

votes

**0**answers

17 views

### Minimum longest acyclic directed path in a graph consisting of two disjoint subgraphs

Consider a simple graph oriented acyclically to obtain a directed graph so as to minimize the longest path. Assume the graph consists of two totally disjoint graphs (empty vertex and edge set ...

**5**

votes

**1**answer

143 views

### When can we make a digraph acyclic by fliping groups of arcs?

We have a digraph D=(V,A) and its arc set A is partitioned into classes. We can flip the classes, which means changing the direction of all the arcs in the class.
Is there any result on when can we ...

**3**

votes

**2**answers

569 views

### Acyclic orientations of complete graphs in terms of Stirling numbers?

It is well-known that the number of acyclic orientations of $K_n$ is $n!$. Does anybody know of a combinatorial argument for this fact which uses the identity:
$$n!=\sum_{k=1}^ns(n,k),$$
where the $...