zbMATH — the first resource for mathematics

Homomorphisms of infinite bipartite graphs onto complete bipartite graphs. (English) Zbl 0543.05058
Let B be a bipartite graph on the vertex sets C, D. A homomorphism \(\phi\) of B onto a complete bipartite graph \(K_{r,s}\) is said to be bicomplete if \(\phi(x)=\phi(y)\) only if either both x, y belong to C, or both x, y belong to D. For a connected bipartite graph B, the author defines the parameter \(\beta_ 0(B)\) as the supremum of all values of min(r,s) for all complete bipartite graphs \(K_{r,s}\) onto which B can be mapped by a bicomplete homomorphism. As the author points out, this parameter \(\beta_ 0(B)\) is closely related to the bichromaticity \(\beta\) (B) which was introduced for finite B by F. Harary, D. Hsu and Z. Miller [Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 236-246 (1978; Zbl 0369.05022)]; however, for infinite B, \(\beta_ 0(B)\) is more interesting than \(\beta\) (B) since one can easily show that \(\beta\) (B) equals the cardinality of the vertex set of B. For infinite B, the author proves two theorems on \(\beta_ 0(B)\) which relate \(\beta_ 0(B)\) to other parameters such as the supremum of the cardinalities of all matchings of B.
Reviewer: T.Andreae

05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: EuDML
[1] Harary F., Hsu D., Miller Z.: The bichromaticity of a tree. Theory and Applocations of Graphs. Proc. Michigan 1976.
[2] Ore O.: Theory of Graphs. Providence 1962. · Zbl 0105.35401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.