Given an undirected connected graph, how many orientations would maintain acyclicity

Question

Given an undirected connected simple graph $G=(V,E)$ there are $2^{|E|}$ orientations. How many of these orientations are acyclic?

Answer 1

I came across a research paper from 1972 which addresses this question. Let $\chi(G, \lambda)$ be the chromatic polynomial. Then $(-1)^{V} \chi(G, -1)$ is the number of acyclic orientations of $G$, your graph. I let $V$ be the vertex count of $G$. This is Theorem 1.3 of the paper.

http://www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf

Answer 2

Very old, but for the sake of completeness, yes, it is well known that we can count

$$ \text{AO}(G) = (-1)^{|V(G)|}\mathcal{X}_G(-1) = T_G(2,0)$$

where $\mathcal{X}_G$ denotes the chromatic polynomial of $G$, and $T_G$ denotes the Tutte polynomial of $G$. You can find a number of papers discussing these results, but the proof of the second inequality is usually done separately from the equality between the Tutte polynomial at $(0,2)$. Tutte polynomial is usually defined on matroids and worked backwards (since any graph $G$ admits a graphic matroid $M(G)$, anything true for $M(G)$ is true for $G$; ie, matroids are more general); there are a number of well-known TG-invariants, of which your question asks about just one. Another is $T_G(0,2)$, which counts the number of totally cyclic orientations instead.

The proofs for each are scattered about, but can dig them up at request.