Constructing trees in bipartite graphs
type: Item
instance of: scholarly article
title: Constructing trees in bipartite graphs
zbMATH Open document ID: 0855.05044
DOI: 10.1016/0012-365X(94)00335-G
author: U. Schulte
published in: Discrete Mathematics
publication date: 1997-01-26T00:00:00Z
review text: It is shown, that if \(G= (V, E)\) is a bipartite graph with more than \((a- 1)|Y|+ (b- 1)|X|- (a- 1)(b- 1)\) edges, where \((X, Y)\) is a vertex partition for \(G\) and \(a\leq b\) are natural numbers with \(a\leq |X|\), \(b\leq |Y|\), then \(G\) contains every tree \(T\) with bipartite numbers \(a\leq b\). This result is related to the Ramsey theory for trees. Let \(a\leq b\), \(T\) an \((a, b)\)-tree, \(G\) the complete bipartite graph with the vertex partition \((X, Y)\) such that \[ |X|= (a- 1) (k+ \sqrt{k(k- 1)}) + 1,\;|Y|= (b- 1) (k+ \sqrt{k(k- 1)})+ 1 \] and let \(\chi\) be an arbitrary coloring of the edges of \(G\) with \(k\) colors. Then \(G\) contains a monochromatic copy of \(T\).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 906917
zbMATH Keywords: bipartite graph
zbMATH Keywords: vertex partition
zbMATH Keywords: tree
zbMATH Keywords: coloring
MaRDI profile type: Publication
cites work: Q3490025
cites work: An upper bound on the Ramsey number of trees
cites work: Q4859947
Wikidata QID: Q126654441
description: scientific article; zbMATH DE number 906917