Mutual placement of bipartite graphs
type: Item
instance of: scholarly article
title: Mutual placement of bipartite graphs
zbMATH Open document ID: 0791.05080
DOI: 10.1016/0012-365X(93)90540-A
published in: Discrete Mathematics
publication date: 1994-06-28T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 473118
zbMATH Keywords: bipartite graph
zbMATH Keywords: biplacement
zbMATH Keywords: 2-placement
author: Jean-Luc Fouquet
author: Adam Paweł Wojda
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: Q4099676
cites work: Q3852212
cites work: Packing trees in complete graphs
cites work: Edge disjoint placement of graphs
cites work: Q3715121
full work available at URL: 0012-365x(93)90540-a
OpenAlex ID: W2085371351
Recommended article: Q3621537
Recommended article: Some results on placing bipartite graphs of maximum degree two
Recommended article: Placing bipartite graphs of small size II
Recommended article: Bipartite permutation graphs
Recommended article: Q4890124
Recommended article: Q4802252
Recommended article: On bipartite‐mixed graphs
Recommended article: Equimatchable bipartite graphs
Recommended article: A class of `matching-equivalent' bipartite graphs
Recommended article: Q5755110
description: scientific article; zbMATH DE number 473118