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

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

-
If you have a cyclic graph, then the answer is simple because you can choose any orientation in which all edges are not pointed the same direction. If you have a graph where all cycles involve a disjoint set of edges, the answer is similarly simple. But if cycles share edges the answer is much more complicated. –  user2566092 Apr 18 '14 at 20:58
@user2566092 Does it make any difference that $G$ is a simple graph? When cycles shared edges, are there any sufficient conditions with which the number of acyclic orientations is known ? (i.e., in/out degrees of the vertices) –  seteropere Apr 18 '14 at 21:24

## 1 Answer

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

-
How easy is it to compute the chromatic polynomial for a graph? –  user2566092 Apr 18 '14 at 21:03
I came across this while researching. However, It is too difficult to me as I am not mathematician and have no good knowledge in graph-theoretic notions. I dont know what is chromatic polynomial or how we compute it. This said, seems I need to understand the paper to come up with the acyclic orientations. ah ! –  seteropere Apr 18 '14 at 21:05
It's NP-Hard to compute the chromatic polynomial. That being said, for a small graph, you may be able to do it by eye-balling it. The term $\lambda$ represents the number of colors. There is another paper I found for computing the Chromatic Polynomial: whitman.edu/mathematics/SeniorProjectArchive/2009/fouts.pdf –  ml0105 Apr 18 '14 at 21:09
@ml0105 Are you aware of anything related to the number of single source single sink orientations? For instance, an upper bound or the exact number of given the chromatic polynomial. –  seteropere May 16 '14 at 19:20