{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:04Z","timestamp":1787323144739,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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 all positive integers $a,b$ and a graph $G$, if the treedepth of $G$ is at least $Cab$, 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)$ either is 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 [Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 234--246]. We also show an application of our techniques 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 $\\mathcal{O}(kt \\log^{3\/2} t)$. This improves upon a bound of $\\mathcal{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 \\cdot \\log_3 ((1+\\sqrt{5})\/2)$.<\/jats:p>","DOI":"10.1137\/19m128819x","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T11:29:18Z","timestamp":1620646158000},"page":"934-947","source":"Crossref","is-referenced-by-count":9,"title":["Improved Bounds for the Excluded-Minor Approximation of Treedepth"],"prefix":"10.1137","volume":"35","author":[{"given":"Wojciech","family":"Czerwi\u0144ski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Nadara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"atypb1","first-page":"1445","author":"Chuzhoy J.","year":"2019","journal-title":"SIAM"},{"key":"atypb2","unstructured":"R. Diestel,\n                      Graph Theory,\n                      2nd ed., Grad. Texts in Math., Springer, Cham, 2000."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.014"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"atypb5","first-page":"234","author":"Kawarabayashi K.","year":"2018","journal-title":"PA"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. Nesetril and P. O. de Mendez,\n                      Sparsity: Graphs, Structures, and Algorithms\n                      , Algorithms Combin. 28, Springer, Cham, 2012,https:\/\/doi.org\/10.1007\/978-3-642-27875-4.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1569-7"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"F. Reidl, P. Rossmanith, F. S. Villaamil, and S. Sikdar,\n                      A faster parameterized algorithm for treedepth\n                      , in Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Copenhagen, Denmark, Part I, J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, eds., Lecture Notes in Comput. Sci. 8572, Springer, Cham, 2014, pp. 931-942,https:\/\/doi.org\/10.1007\/978-3-662-43948-7_77.","DOI":"10.1007\/978-3-662-43948-7_77"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90161-0"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M128819X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:09Z","timestamp":1787319849000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M128819X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M128819X"],"URL":"https:\/\/doi.org\/10.1137\/19m128819x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}