8
$\begingroup$

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$).
$\endgroup$
  • 3
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Apr 28 '14 at 3:09
  • $\begingroup$ @YuvalFilmus thanks a lot. so its a matter of evaluating the polynomial at $-\lambda$. $\endgroup$ – seteropere Apr 28 '14 at 18:44
5
$\begingroup$

As Yuval noted, you can count the number of acyclic orientations by evaluating the chromatic polynomial of a graph at negative unity. For computing chromatic polynomials, there are efficient algorithms known for some graph classes.

There is also a recursive algorithm for generating all acyclic orientations of a graph given by Squire [1]. 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.


[1] Squire, M. B. (1998). Generating the acyclic orientations of a graph. Journal of Algorithms, 26(2), 275-290.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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