# 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. – Saeed 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)? – András Salamon 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$. – seteropere 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$? – seteropere Feb 28 '15 at 1:02