Premium
Ramsey‐type results for oriented trees
Author(s) -
Kohayakawa Yoshiharu,
Łuczak Tomasz,
Rödl Vojtěch
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199605)22:1<1::aid-jgt1>3.0.co;2-s
Subject(s) - arrow , combinatorics , mathematics , vertex (graph theory) , graph , tree (set theory) , path (computing) , discrete mathematics , computer science , programming language
For a graph G and a digraph (RIGHT ARROW ABOVE H), we write G → (RIGHT ARROW ABOVE H) (respectively, G (A ABOVE RIGHT ARROW)(RIGHT ARROW ABOVE H) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of (RIGHT ARROW ABOVE H). In this note we study how small the graphs G such that G → (RIGHT ARROW ABOVE H) or such that G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE H) may be, if (RIGHT ARROW ABOVE H) is a given oriented tree (RIGHT ARROW ABOVE 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 (RIGHT ARROW ABOVE 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 → (RIGHT ARROW ABOVE T) n for any such tree (RIGHT ARROW ABOVE T) n . This last result turns out to be nearly best possible as it is shown that any graph G with G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE P) n , where (RIGHT ARROW ABOVE 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.