Say a finite simple graph $G$ is skeletal if there is a partial order $\leqslant$ on the vertices of $G$ with an edge between $v_1$ and $v_2$ iff $v_1$ and $v_2$ are comparable. (That is, if $v_1\leqslant v_2$ or $v_2\leqslant v_1$). Claim: All skeletal graphs are "divisibility" and visa versa. Proof: Well-known, see, for example, this post $\Box$ Now, consider some permutation $\pi:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$. Observe that the relations $i<_{*} j\iff i<j\text{ and }\pi(i)<\pi(j)$ and $i<^{*} j\iff i<j\text{ and }\pi(i)>\pi(j)$ over the elements of $\{1,2,\dots,n\}$ both give rise to partial orders on said set. It follows that if a graph $G$ is "permutationary", then both $G$ and $\overline{G}$ are skeletal, and are thus both "divisibility." Alternatively, suppose there is some $G$ for which both $G$ and $\overline{G}$ are "divisibility" (and thus one for which both of the aforementioned graphs are skeletal). By definition we have partial orders $\leqslant_{*},\leqslant^{*}$ (irrespectively) over the vertices of $G$ such that for any two vertices $v_1,v_2$, exactly one of $$v_1\leqslant_{*} v_2\text{ or }v_2\leqslant_{*} v_1$$And $$v_1\leqslant^{*} v_2\text{ or }v_2\leqslant^{*} v_1$$Holds. In particular, we may define a total order $\leq$ on the set of vertices of $G$ by simply "combining" the data of $\leqslant_{*}$ and $\leqslant^{*}$. (One may show that no "contradictions" can possibly arise as we define our relations.) Identify the vertices of $G$ with the elements of $\{1,2,\dots,n\}$ in accordance with $\leq$. Now let $S_0=\{1,2,\dots,n\}$, and construct the permutation $\pi:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$ inductively as follows: Define $\pi(i)$ to be the $k^{\text{th}}$ smallest element of $S_{i-1}$ where $k=1+|\{i\in \{1,2,\dots,n\}:1<^{*}i\}|$ and $S_i=S_{i}\setminus\{\pi(i)\}$, iterating the algorithm until $S_n=\emptyset$ is reached. It can be shown that $G$ is the "permutation" graph corresponding to $\pi$, as desired $\blacksquare$

This problem appeared as Lemma $3.51$ and Theorem $3.6$ ($(1) \Leftrightarrow (3)$) in B.Dushnik and E.W.Miller's article Partially order sets in 1941. Let me summarize the key points below: (the red words "check" remind us that we omit the details) $1).$ Definition: A finite simple graph $G$ is called a "partial order" graph if there exists a partial order $\preceq$ on $V(G)$ such that for any two distinct vertices $v,v'$, we have $vv' \in E(G)$ if and only if $v$ and $v'$ are comparable in $\preceq$ (i.e. $v \preceq v'$ or $ v' \preceq v$). (as rafayaashary1's definition "skeletal". by the way, literally we should call $G$ a "partial orderable" graph and call $(G,\preceq)$ a "partial ordered" graph) $2)$ Easy Fact 1: a simple graph $G$ is a "divisibility" graph if and only if it is a "partial order" graph. $3)$ Easy Fact 2: if $G$ is a "permutationary" graph with the permutation $\pi$ and $V(G) = \{1,2,\cdots,n\}$. We define two relations $\preceq_1$ and $\preceq_2$ as $$i \preceq_1 j \text{\quad if and only if \quad } i \leq j \text{\quad and \quad } \pi(i) \geq \pi(j)$$$$i \preceq_2 j \text{\quad if and only if \quad } i \leq j \text{\quad and \quad } \pi(i) \leq \pi(j)$$then it can be checked that both $(G, \preceq_1)$ and $(\overline{G}, \preceq_2)$ are "partial order" graphs. So $G$ is a "permutationary" graph $\Rightarrow$ both $G$ and $\overline{G}$ are "partial order" graphs. $4)$ Easy But Trivial Fact If $(G, \preceq_1)$ and $(\overline{G}, \preceq_2)$ are both "partial order" graph. Define two relations $\preceq$ and $\preceq'$ as follows, for any two distinct vertices $v,v' \in V(G)$, $$v \preceq v' \text{\quad if and only if \quad } (v \preceq_1 v' \text{\quad or \quad } v \preceq_2 v')$$$$v \preceq' v' \text{\quad if and only if \quad } (v \preceq_1 v' \text{\quad or \quad } v' \preceq_2 v)$$Then both $\preceq$ and $\preceq'$ are total orders. (This is the lemma 3.51, it need some work to check the transitivity and they are indeed total orders.) Now, since $\preceq$ is a total order, we can lable $V(G)$ as $$v_1 \prec v_2 \cdots \prec v_n.$$Since $\preceq'$ is another total order, we can list vertices in another way, i.e. there exists a permutation $\pi$ on $\{ 1,2,\cdots,n \}$ such that $$v_{\pi^{-1}(n)} \prec' v_{\pi^{-1}(n-1)} \prec' \cdots \prec' v_{\pi^{-1}(1)}.$$We can check that $(G,\pi)$ is a "permutationary" graph. So $G$ and $\overline{G}$ are both "partial order" graph $\Rightarrow$ $G$ is a "permutationary" graph. (This is theorem 3.61 presented in our terminology.) A personal note: I discussed this problem with teachers and students at Xuejun High School in September, 2018.

Quite a nice problem! First, suppose the graph is permutationary, and suppose the permutation is given by $\pi$. We can label the vertex $i$ by $2^i 3^{n-\pi(i)}$ to show that the graph is divisibility, and we can label by $2^i 3^{\pi(i)}$ to show that the complement of the graph is divisibility. Now, we show that if the graph $G$ and its complement are divisibility, then it is permutationary. Fix the labelings of $G$ and its complement with distinct positive integers satisfying the divisibility conditions. Let $T$ be a tournament on the vertex set of $G$ defined as follows: draw $i\to j$ if the label of $i$ divides the label of $j$ in either $G$ or the complement, depending on which one contains the edge $ij$. The main claim is as follows. Claim: The tournament $T$ is acylic. Proof: Label the edge $i\to j$ red if it is in $G$, and black otherwise. Suppose for sake of contradiction that $T$ had a (directed) cycle. Consider a cycle of minimal length. Note that if the cycle has two consecutive edge of the same color, say $a\to b$ and $b\to c$, then we must also have the edge $a\to c$. This makes the cycle shorter, which contradicts minimality. Thus, the cycle alternates red and black. Consider a portion of the cycle $z\to a\to b\to c\to d$, where $za$ is black, $ab$ is red, $bc$ is black, and $cd$ is red. Now, we must have $a\to c$, otherwise we get a smaller cycle. If $ac$ is red, then we get $a\to d$ which makes the cycle shorter, and if it is black, then we get $z\to c$, which makes the cycle shorter. Thus, in all cases, the cycle can be made shorter, which is the desired contradiction. $\blacksquare$ Thus, we can assign each vertex of $T$ a label from $1$ through $n$ such that $i\to j$ if and only if $i<j$. Now, change the original divisibility labeling of $G$ from $x$ to $N/x$ where $N$ is the lcm of all the labels. This switches all the red arrows in $G$, but the claim still holds. Consider the similar labeling of the vertices using $1$ through $n$. Let the label of the vertex originally labeled $i$ be $\pi(i)$. It is easy to see that $\pi$ has an inversion $ij$ if and only if $ij$ is an edge in $G$, so we're done.

good job