✦ LIBER ✦

Monochromatic coverings and tree Ramsey numbers

✍ Scribed by Zsolt Tuza

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 499 KB
Volume: 125
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90179-1

No coin nor oath required. For personal study only.

✦ Synopsis

Let k = 3 or 4, and let n be a natural number not divisible by k -1. Consider any edge coloring of the complete graph K of order (k-l)(n-1)+2 with k colors. The following facts were known previously: (i) K contains a monochromatic connected subgraph on more than n vertices. (ii) There are k -1 monochromatic connected subgraphs whose union covers the entire vertex set of K.

We prove that the requirements of (i) and (ii) can be fulfilled simultaneously, i.e. (iii) There are k -1 monochromatic connected subgraphs G, , , G,_ r such that 1 V(G, )I > n + 1 and V(G,)u~~~uV(Gt_,)= V(K).

📜 SIMILAR VOLUMES

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).

Small order graph-tree Ramsey numbers

✍ R.J. Faudree; C.C. Rousseau; R.H. Schelp 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 521 KB

With but a few exceptions, the Ramsey number r(G, T) is determined for all connected graphs G with at most five vertices and all trees T.

Vertex coverings by monochromatic cycles

Vertex coverings by monochromatic cycles and trees

✍ P Erdős; A Gyárfás; L Pyber 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 346 KB

Extremal theory and bipartite graph-tree

Extremal theory and bipartite graph-tree Ramsey numbers

✍ P. Erd'́os; R.J. Faudree; C.C. Rousseau; R.H. Schelp 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 675 KB

For a positive integer n and graph E, fs(n) is the least integer m such that any graph of order n and minimal degree m has a copy of B. It will be show that if B is a bipartite graph with parts of order k and 1 (k G I), then there exists a positive constant c, such that for any tree T,, of order II

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

The tripartite Ramsey number for trees

✍ Julia Böttcher; Jan Hladký; Diana Piguet 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 338 KB

## 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