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.