Improved bounds for the excluded-minor approximation of treedepth.

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for every integers a, b >= 2 and a graph G, if the treedepth of G is at least Cab log a, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph. As a direct corollary, we obtain that every graph of treedepth Omega(k(3) log k) is either of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2(k). This improves the bound of Omega(k(5) log(2) k) of Kawarabayashi and Rossman [SODA 2018]. We also show an application for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width O(kt log(3/2) t). This improves upon a bound of O(kt(2) log t) stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d center dot log(3)((1 + root 5)/2).