# An upper bound over the number of bipolar orientations for a regular graph

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.

• 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. Jun 25 '14 at 23:27
• 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)? Jun 26 '14 at 8:52
• @AndrásSalamon I know this is terribly late. The only additional condition is that $G$ is a hypercube with dimension $d$. Feb 28 '15 at 6:45

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.
• Thanks. Does it make any difference if $G$ is a hypercube graph with dimension $d$? Feb 28 '15 at 1:02