3-biplacement of bipartite graphs

Abstract

Let $G=(L,R;E)$ be a bipartite graph with color classes $L$ and $R$ and edge set $E$. A set of two bijections ${\varphi_1 , \varphi_2}$, $\varphi_1 , \varphi_2 :L \cup R \to L \cup R$, is said to be a $3$-biplacement of $G$ if $\varphi_1(L)= \varphi_2(L) = L$ and $E \cap \varphi_1^(E)=\emptyset$, $E \cap \varphi_2^(E)=\emptyset$, $\varphi_1^(E) \cap \varphi_2^(E)=\emptyset$, where$\varphi_1^$, $\varphi_2^$ are the maps defined on $E$, induced by $\varphi_1$, $\varphi_2$, respectively. We prove that if $|L|=p$, $|R|=q$, $3 \leq p \leq q$, then every graph $G=(L,R;E)$ of size at most $p$ has a $3$-biplacement.