Constructing trees in bipartite graphs (Q1918569): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 15:41, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Constructing trees in bipartite graphs |
scientific article |
Statements
Constructing trees in bipartite graphs (English)
0 references
26 January 1997
0 references
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\).
0 references
bipartite graph
0 references
vertex partition
0 references
tree
0 references
coloring
0 references