<p>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.</p>

CC BY-SA 3.0
2015-02-28T01:02:13.413Z
Thanks. Does it make any difference if $G$ is a hypercube graph with dimension $d$?
seteropere
CC BY-SA 3.0
2014-06-25T23:14:58.277Z
2014-06-25T23:14:58.277Z
David Eppstein
<p>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? </p>

<p>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.</p>

CC BY-SA 3.0
2014-06-25T23:27:10.360Z
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
CC BY-SA 3.0
2014-06-26T08:52:53.817Z
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
CC BY-SA 3.0
2015-02-28T06:45:35.547Z
@AndrásSalamon I know this is terribly late. The only additional condition is that $G$ is a hypercube with dimension $d$.
seteropere
<graph-theory><polynomials>
An upper bound over the number of bipolar orientations for a regular graph
seteropere
# An upper bound over the number of bipolar orientations for a regular graph

(Asked by: username_0 on 2014-05-24)

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.

**Tags:** graph-theory, polynomials

> **Comments:**
> **username_1**: 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.  
> **username_2**: As username_3 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)?  
> **username_0**: @AndrásSalamon I know this is terribly late. The only additional condition is that $G$ is a hypercube with dimension $d$.  

---

## 1 answers

### Answer by username_3 on 2014-06-25. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks. Does it make any difference if $G$ is a hypercube graph with dimension $d$?  

---

