# Algorithm to find all acyclic orientations of a graph

I am working on acyclic orientations of undirected graphs and have the following questions:

1. Given connected undirected simple graph $G$, how to find all possible acyclic orientations of $G$ ?
2. What is the number of acyclic orientations? It is known (from here) to be $(-1)^p\ \chi(G,-\lambda)$ for a graph $G$ with $p$ vertices where $\chi$ is the chromatic polynomial evaluated at $-\lambda$; but I wasn't successful in understanding how to evaluate $\chi$ at a negative value ($-\lambda$).
• Re 2, $\chi(G,\cdot)$ is just a polynomial. It can be evaluated at any complex point. The number of acyclic orientations is $(-1)^p \chi(G,-1)$, where $p$ is the number of vertices. For example, the chromatic polynomial of a triangle is $t(t-1)(t-2)$, and so the number of acyclic orientations is $(-1)^3(-1)(-2)(-3) = 6$ (all $2^3$ orientations other than the $2$ cyclic orientations). Apr 28, 2014 at 3:09
• @YuvalFilmus thanks a lot. so its a matter of evaluating the polynomial at $-\lambda$. Apr 28, 2014 at 18:44

There is also a recursive algorithm for generating all acyclic orientations of a graph given by Squire . The algorithm requires $O(n)$ time per acyclic orientation generated. Roughly 20 years ago this was the fastest algorithm known; it's possible a faster one is known now, or that you can improve Squire's algorithm by known techniques.