✦ LIBER ✦

Bichromaticity of bipartite graphs

✍ Scribed by Dan Pritikin

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 312 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090410

No coin nor oath required. For personal study only.

✦ Synopsis

Let 8 be a bipartite graph with edge set €and vertex bipartition M, N.

The bichromaticity p ( 6) is defined as the maximum number p such that a complete bipartite graph on p vertices is obtainable from 5 by a sequence of identifications of vertices of M or vertices of N. Let p = max{lMI, IN}. Harary, Hsu, and Miller proved that P(8) 2 p + 1 and that p(T) = p + 1 for Tan arbitrary tree. We prove that P(B) I p + l € / / p yielding a simpler proof that p(T) = p + 1. We also characterize graphs for which KP.2 is obtainable by such identifications. For OK, the graph of the K-dimensional cube, we obtain the inequality 2K-' + 2tlog2 ' J 9 ( w ) = W ' .

📜 SIMILAR VOLUMES

The bichromaticity of cylinder graphs an

The bichromaticity of cylinder graphs and torus graphs

✍ Dan Pritikin 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 420 KB

The bichromaticity of a bipartite graph B is defined as the maximum value of r + s for which B has the complete bipartite graph K,, as a homomorphic image We determine the bichromaticity of any bipartite cylinder graph C2,, x P, or torus graph CZn x C , , In the process, w e disprove a conjecture of

Embeddings of bipartite graphs

✍ Mohammed Abu-Sbeih; T. D. Parsons 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB

Koszul Bipartite Graphs

✍ Hidefumi Ohsugi; Takayuki Hibi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 48 KB

Cellular Bipartite Graphs

✍ Hans-Jürgen Bandelt; Victor Chepoi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 310 KB

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Neighborhood hypergraphs of bipartite gr

Neighborhood hypergraphs of bipartite graphs

✍ Endre Boros; Vladimir Gurvich; Igor Zverovich 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB

## Abstract Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the litera