## Ramsey-Type Results for Oriented Trees

### Authors:

- Yoshiharu Kohayakawa,
- Tomasz Łuczak,
- Vojtěch Rödl

### Abstract

For a graph G and a digraph H
^{→}
, we write G → H
^{→}
(respectively, G →
^{a}
H
^{→}
) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of H
^{→}
. In this note we study how small the graphs G such that G → H
^{→}
or such that G →
^{a}
H
^{→}
may be, if H
^{→}
is a given oriented tree T
^{→n}
on n vertices. We show that there is a graph on O(n
^{4}
log n) vertices and O(n
^{6}
(log n)
^{2}
) edges such that G → T
^{n}
for every n-vertex oriented tree T
^{→n}
. We also prove that there exists a graph G with O(n
^{2}
log n) vertices and O(n
^{3}
(log n)
^{2}
) edges such that G →
^{a}
T
^{→n}
for any such tree T
^{→n}
. This last result turns out to be nearly best possible as it is shown that any graph G with G →
^{a}
P
^{→n}
, where P
^{→n}
is the directed path of order n, has more than n
^{2}
/2 vertices and more than [n/3]
^{3}
edges if n ≥ 3.© 1996, John Wiley & Sons, Inc.

- Record ID
- UAM4cc5e3ca9be649ea8c6a66d955d33959
- Author
- Journal series
- Journal of Graph Theory, ISSN 0364-9024
- Issue year
- 1996
- Vol
- 22
- Pages
- 1-8
- ASJC Classification
- DOI
- DOI:10.1002/(SICI)1097-0118(199605)22:1<1::AID-JGT1>3.0.CO;2-S opening in a new tab
- Language
- en English
- Score (nominal)
- 25
- Score source
- journalList
- Publication indicators
- = 1.000; : 1999 = 1.122; : 2006 = 0.403 (2) - 2007=0.661 (5)

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM4cc5e3ca9be649ea8c6a66d955d33959/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.

Back