Abstract
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 * log_3 ((1+sqrt{5})/2).
BibTeX  Entry
@InProceedings{czerwinski_et_al:LIPIcs:2019:11155,
author = {Wojciech Czerwinski and Wojciech Nadara and Marcin Pilipczuk},
title = {{Improved Bounds for the ExcludedMinor Approximation of Treedepth}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {34:134:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11155},
URN = {urn:nbn:de:0030drops111557},
doi = {10.4230/LIPIcs.ESA.2019.34},
annote = {Keywords: treedepth, excluded minor}
}
Keywords: 

treedepth, excluded minor 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 