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.