Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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 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 at 21:24

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
How easy is it to compute the chromatic polynomial for a graph? –  user2566092 Apr 18 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 at 21:05
1  
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 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 at 19:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.