Opuscula Math.
28
, no. 3
(), 223-231
Opuscula Mathematica

# 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.
Keywords: bipartite graph, packing of graphs, placement, biplacement.
Mathematics Subject Classification: 05C70.