✦ LIBER ✦

Ramsey-type results for oriented trees

✍ Scribed by Kohayakawa, Yoshiharu; ?uczak, Tomasz; R�dl, Vojt?ch

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 486 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199605)22:1<1::aid-jgt1>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

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 vertices. We show that there is a graph on O(n410g n) vertices and O(n6(log n)*) edges such that G-T" for every n-vertex oriented tree b. We also prove that there exists a graph G with O(n2 log n) vertices and O(n3(log n)') edges such that G 5 ?" for any such tree ?". This last result turns out to be nearly best possible as it is shown that any graph G with G Z p", where is the directed path of order n, has more than n2/2 vertices and more than [n/3j3 edges if n P 3.

📜 SIMILAR VOLUMES

Ramsey-type results for Gallai colorings

✍ András Gyárfás; Gábor N. Sárközy; András Sebő; Stanley Selkow 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

## Abstract A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐co

A Ramsey-type result for the hypercube

✍ Noga Alon; Radoš Radoičić; Benny Sudakov; Jan Vondrák 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB

We prove that for every fixed k and ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Q n with k colors contains a monochromatic cycle of length 2 . This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which a

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

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

A ramsey-type bound for rectangles

✍ T�th, G�za 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

It is proved that for any rectangle T and for any 2-coloring of the points of the 5dimensional Euclidean space, one can always find a rectangle T' congruent to T , all of whose vertices are of the same color. We also show that for any k-coloring of the k2 + o(k2)-dimensional space, there is a monoch

Ramsey-Type Theorems for Spatial Graphs

Ramsey-Type Theorems for Spatial Graphs and Good Drawings

✍ Seiya Negami 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 336 KB

We shall prove that for any spatial graph H, there exists a pair of natural numbers (N, M) such that any spatial embedding of the complete bipartite graph K N, M whose projection is a good drawing on the plane contains a subgraph which is ambient isotopic to a subdivision of H. ## 1998 Academic Pre