Abstract:Huynh, Joret, Micek, Seweryn, and Wollan (Combinatorica, 2022) introduced a graph parameter, later referred to as 2-treedepth and denoted $\mathrm{td}_2(\cdot)$. 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).
From: Jędrzej Hodor [view email]
[v1]
Wed, 6 Aug 2025 13:41:20 UTC (170 KB)
[v2]
Sun, 14 Sep 2025 19:05:30 UTC (108 KB)
[v3]
Wed, 29 Jul 2026 10:05:10 UTC (110 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。