✦ LIBER ✦

The tripartite Ramsey number for trees

✍ Scribed by Julia Böttcher; Jan Hladký; Diana Piguet

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 338 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20582

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that for all ε>0 there are α>0 and n~0~∈ℕ such that for all n⩾n~0~ the following holds. For any two‐coloring of the edges of K~n, n, n~ one color contains copies of all trees T of order t⩽(3 − ε)n/2 and with maximum degree Δ(T)⩽n^α^. This confirms a conjecture of Schelp. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 264–300, 2012

📜 SIMILAR VOLUMES

Tripartite Ramsey numbers for paths

✍ András Gyárfás; Miklós Ruszinkó; Gábor N. Sárközy; Endre Szemerédi 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph __K__(__n__, __n__, __n__) there is a monochromatic path of length (1 − __o__(1))2__n__. Since __R__(__P__~2__n__+1~,__P__~2__n__+1~)=3__n__,

Local and Mean Ramsey Numbers for Trees

✍ B. Bollobás; A. Kostochka; R.H. Schelp 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 75 KB

In this note we find the local and mean k-Ramsey numbers for many trees for which the Erdo s So s tree conjecture holds. ## 2000 Academic Press The usual Ramsey number R(G, k) is the smallest positive integer n such that any coloring of the edges of K n by at most k colors contains a monochromatic

Tree-complete graph ramsey numbers

✍ V. Chvátal 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB

## Abstract The ramsey number of any tree of order __m__ and the complete graph of order __n__ is 1 + (__m__ − 1)(__n__ − 1).

On the Ramsey number of trees versus gra

On the Ramsey number of trees versus graphs with large clique number

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3

Ramsey Numbers for Matroids

✍ Talmage James Reid 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 233 KB

Ramsey-type results for oriented trees

✍ Kohayakawa, Yoshiharu; ?uczak, Tomasz; R�dl, Vojt?ch 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 486 KB

For a graph G and a digraph h, w e write Gfi (respectively, G 5 2) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of k In this note w e study how small the graphs G such that Gor such that G 5 i/ may be, if k is a given oriented tree ? on n vert