2025/08/06 by Jędrzej Hodor, Freddie Illingworth, Hodor, Jędrzej +3
Mathematics · #math.CO
paper · pdf · doi:10.48550/arxiv.2508.04445
18 pages
arxiv created 2026/07/29 · arxiv updated 2026/07/30
Huynh, Joret, Micek, Seweryn, and Wollan (Combinatorica, 2022) introduced a graph parameter, later referred to as 2-treedepth and denoted td2(⋅). The parameter is the natural 2-connected version of treedepth. For every graph, 2-treedepth is at most the treedepth but can be much smaller: long paths have arbitrarily large treedepth but 2-treedepth equal to 2. We prove a converse showing that every graph with no induced path on t vertices and 2-treedepth at most k has treedepth at most g(k, t). In fact, we determine the value of the function g up to a multiplicative factor of 2. Additionally, we give asymptotically tight bounds for the problem of forcing long induced paths in graphs with long paths and bounded 2-treedepth or bounded pathwidth. The latter result answers a question of Hilaire and Raymond (E-JC, 2023).