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.

$\endgroup$
  • 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 Jun 25 '14 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 Jun 26 '14 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 Feb 28 '15 at 6:45
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Does it make any difference if $G$ is a hypercube graph with dimension $d$? $\endgroup$ – seteropere Feb 28 '15 at 1:02

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.