2
$\begingroup$

Given a $k$-regular graph $G$, the number of acyclic orientations $Acy(G)$ is $\chi(-1)$ where $\chi$ is the chromatic polynomial of $G$. How many bipolar orientations does $G$ have?

Is there an upper bound for it? I assume it should be exponentially lower than $Acy(G)$ but didn't succeed in finding a known result connecting these two numbers.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ For any graph $G$ there is a graph $G'$ which is exactly same as $G$ except that two extra vertices $u,v$ which are connected to all other vertices such that $bi(G')\ge Acy(G)$ (just make them source and sink). So if there is some function (e.g related to the density of a graph) then that relation does not look like exponential. $\endgroup$
    – Saeed
    Commented Jun 25, 2014 at 23:27
  • 1
    $\begingroup$ As David Eppstein points out, every acyclic orientation is a bipolar orientation. Did you mean "exponentially larger"? If so, did you have additional conditions in mind to avoid the case of the disconnected graph (where acyclic and bipolar orientations coincide)? $\endgroup$
    – András Salamon
    Commented Jun 26, 2014 at 8:52
  • $\begingroup$ @AndrásSalamon I know this is terribly late. The only additional condition is that $G$ is a hypercube with dimension $d$. $\endgroup$
    – seteropere
    Commented Feb 28, 2015 at 6:45

1 Answer 1

Reset to default
3
$\begingroup$

It is not always lower than the number of acyclic orientations by any factor, let alone an exponential one. In particular, in a complete graph, there are $n!$ acyclic orientations, all of which are bipolar.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Does it make any difference if $G$ is a hypercube graph with dimension $d$? $\endgroup$
    – seteropere
    Commented Feb 28, 2015 at 1:02

Your Answer

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

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