ROOTED INDUCED TREES IN TRIANGLE-FREE GRAPHS

ABSTRACT. For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. Further, for a vertex v ∈ V (G), let t(G, v) denote the maximum number of vertices in an induced subgraph of G that is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle-free graphs G (and vertices v ∈ V (G)) on n vertices is denoted by t3(n) (t∗3(n)). Clearly, t(G, v) ≤ t(G) for all v ∈ V (G). In this note, we solve the extremal problem of maximizing |G | for given t(G, v), given that G is connected and triangle-free. We show that |G | ≤ 1+ (t(G,v)−1)t(G,v) 2 and determine the unique extremal graphs. Thus, we get as corollary that t3(n) ≥ t∗3(n) = d 12 (1 + 8n − 7)e, improving a recent result by Fox, Loh and Sudakov. All graphs in this note are simple and finite. For notation not defined here we refer the reader to Diestel’s book [1]. For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. The problem of bounding t(G) was first studied by Erdős, Saks and Sós [2] for certain classes of graphs, one of them being triangle-free graphs. Let t3(n) be the minimum of t(G) over all connected triangle-free graphs G on n vertices. Erdős, Saks and Sós showed that Ω log n log logn ≤ t3(n) ≤ O( n log n). This was recently improved by Matous̆ek and S̆ámal [4] to ec logn ≤ t3(n) ≤ 2 n + 1, for some constant c. For the upper bound, they construct graphs as follows. For k ≥ 1, let Bk be the bipartite graph obtained from the path P k = v1... vk if we replace vi by k+12 − |k+12 − i | independent vertices for 1 ≤ i ≤ k. This graph has |Bk |