Is there an appropriate labeling for the colored graph Motivation:
For those of you who care to know, I thought about this question after looking at this question.
Let $X=\{1,2,\dots,N\}$, and let $f:X\to X$ be a bijection.  We define the two-colored (complete) graph $G(f)$ on $N$ nodes as follows:
Label the nodes $1,2,\dots ,N$. Take any $1\leq i<j\leq N$, and color the edge $e_{ij}$ by the 
following scheme: if $f(i)<f(j)$, let $e_{ij}$ be red.  Otherwise, (if $f(i)>f(j)$) let $e_{ij}$ be blue

Question:

Given $N$ unlabeled nodes and a complete two-colored graph, can we label the nodes in such a way that the resulting graph is $G(f)$ for $X=\{1,2,\dots,N\}$ and some bijection $f:X\to X$? 

It's clear to me that some labelings won't work on some graphs.  For example, the graph with red edges $\color{red}{1\mapsto 2},\color{red}{2\mapsto 3}$ and the blue edge $\color{blue}{1 \mapsto 3}$ does not correspond to any valid bijection, but we can relabel this graph appropriately as $\color{blue}{1\mapsto2},\color{red}{2\mapsto3,1\mapsto3}$ corresponding to the bijection $\{1,2,3\}\overset{f}{\to}\{2,1,3\}$.
On the other hand, any monochromatic graph admits all labelings.
Any information regarding this (or a similar problem I might not have heard of) is very much appreciated. 
 A: It seems that the answer is negative for large $N$ , because for the complete graph on $N$ vertices the number $2^{N(N-1)/2}$ of different colorings is asymptotically greater than the number $N!$ of different labelings.
A: After writing a Python script to exhaust the possibilities, I have determined that there is no bijection corresponding to the following graph:
$$
\color{red}{1\mapsto 2\mapsto3\mapsto4\mapsto5\mapsto1}\\
\color{blue}{1\mapsto3\mapsto5\mapsto2\mapsto4\mapsto1}
$$
The only explanation I have as of now is that I've checked all $5!$ possibilities, and there is no $f$ such that $G_f$ has a blue (or red) degree of $2$ at each node.
Added by Alex Ravsky. It seems I can explain why the graph has no bijections. (Since my explanation is too big and formatted, I think it would be better to add it to the answer body instead to write it as a comment). Let $X=\{1,2,3,4,5\}$ be its set of vertices, $g:X\to X$ be a labeling of the graph and $f:X\to X$ be a bijection such that for 
every $1\leq g(i)<g(j)\leq 5$, if $fg(i)<fg(j)$ then $e_{ij}$ is red and otherwise $e_{ij}$ is blue.
Now let $i,j,k$ be the consequent numbers of a cyclic sequence $\{\dots,1,2,3,4,5,1,2,\dots\}$. Then the edges $e_{ij}$ and $e_{jk}$ are red and $e_{ik}$ is blue. Then the following condition holds: 
$$[[(g(i)<g(j))\&(fg(i)<fg(j))]\vee[(g(i)>g(j))\&(fg(i)>fg(j))]]\&$$
$$[[(g(j)<g(k))\&(fg(j)<fg(k))]\vee [(g(j)>g(k))\&(fg(j)>fg(k))]]\&$$
$$[[(g(i)<g(k))\&(fg(i)>fg(k))]\vee [(g(i)>g(k))\&(fg(i)<fg(k))]].$$
It implies that both cases $g(i)<g(j)<g(k)$ and $g(i)>g(j)>g(k)$ are impossible. 
Hence the map $g$ satisfies one of the conditions: $$g(1)>g(2)<g(3)>g(4)<g(5)>g(1)<g(2)>\dots$$ or $$g(1)<g(2)>g(3)<g(4)>g(5)<g(1)>g(2)<\dots.$$ Both are contradictions.
