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$).
Improve this question
$\endgroup$
2
  • 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, 2014 at 3:09
  • $\begingroup$ @YuvalFilmus thanks a lot. so its a matter of evaluating the polynomial at $-\lambda$. $\endgroup$
    – seteropere
    Apr 28, 2014 at 18:44

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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