Mutual placement of bipartite graphs (Q1309454)

Let \(G=(L,R,E)\) denote a bipartite graph \(G\) having bipartition \((L,R)\) and edge set \(E\). A bipartite graph \(G=(L,R,E)\) such that \(| L |=p\) and \(| R |=q\) is called a \((p,q)\)-bipartite graph. Suppose \(G=(L,R,E)\) and \(H=(L',R',E')\) are two bipartite graphs. A bijection \(\phi:L \cup R \to L' \cup R'\) is said to be a biplacement of \(G\) and \(H\) if \(\phi(L)=L'\) (which implies that \(\phi (R)=R')\) and \(\phi(x) \phi (y) \notin E'\) for any edge \(xy\) of \(G\). A biplacement of a bipartite graph \(G\) with a copy of \(G\) is called a 2-placement of \(G\). Note that the order of writing the two parts \(L\) and \(R\) in \(G=(L,R,E)\) is important in the study of biplacements of \(G\) and \(H=(L',R',E')\). In this paper the authors prove that, with some exceptions, every bipartite graph \(G\) of order \(n\) and size at most \(n-2\) has a 2- placement. They also give some sufficient conditions for bipartite graphs \(G\) and \(H\) to have a biplacement. A typical result is as follows: Suppose \(G\) and \(H\) are two \((p,p)\)-bipartite graphs such that \(e(G) \leq 2p\) and \(e(H) \leq p-2\). Then there is a biplacement of \(G\) and \(H\).