Large homeomorphically irreducible trees in path‐free graphs

A subgraph of a graph is a homeomorphically irreducible tree (HIT) if it is a tree with no vertices of degree two. Furuya and Tsuchiya [Discrete Math. 313 (2013), pp. 2206–2212] proved that every connected P 4 ‐free graph of order n ≥ 5 has a HIT of order at least n − 1 , and Diemunsch et al [Discrete Appl. Math. 185 (2015), pp. 71–78] proved that every connected P 5 ‐free graph of order n ≥ 6 has a HIT of order at least n − 2 . In this paper, we continue the study of HITs in path‐free graphs and bring to a conclusion proving the following three results: (a) If a connected graph F satisfies the condition that every connected F ‐free graph G has a HIT of order Ω ( ∣ V ( G ) ∣ ) , then F is a path of order at most 7 . (b) Every connected P 6 ‐free graph of order n ≥ 9 has a HIT of order at least ( n + 1 ) / 2 . (c) Every connected P 7 ‐free graph of order n ≥ 9 has a HIT of order at least ( n + 3 ) / 3 . Furthermore, we focus on a P 6 ‐free graph having large minimum degree, and prove that for a connected P 6 ‐free graph G of order n ≥ 11 , if δ ( G ) ≥ 3 , then G has a HIT of order greater than ( δ ( G ) n / δ ( G ) + 1 ) − 1 .