treedepth

• 2019/01 Ganian2019
  • treedepth $k$ upper bounds shrub-depth by $\mathcal O(k)$ – Proposition 3.2. If $G$ is of tree-depth $d$, then $G \in \mathcal{TM}_{2^d}(d)$. …
• 2019 Sorge2019
  • page 11 : treedepth $k$ upper bounds pathwidth by $\mathcal O(k)$ – Lemma 4.27. The treedepth $t$ strictly upper bounds the pathwidth $p$. We have $p \le t$.
• 2010/08 Sasak2010
  • page 32 : graph class grid has unbounded treedepth – Corollary 2.24 Tree-depth of a grid is at least $\lceil \log_2(n+1)\rceil$.
• 2008 gradnesetril2008
  • d-path-free $k$ upper bounds treedepth by $k^{\mathcal O(1)}$
  • treedepth $k$ upper bounds d-path-free by $2^{\mathcal O(k)}$
• https://en.wikipedia.org/wiki/Tree-depth
  • treedepth – The tree-depth of a graph $G$ may be defined as the minimum height of a forest $F$ with the property that every edge of $G$ connects a pair of nodes that have an ancestor-descendant relationship to each other in $F$.
• SchroderThesis
  • page 11 : treedepth $k$ upper bounds diameter by $\mathcal O(k)$ – Proposition 3.1
  • page 21 : bounded treedepth does not imply bounded distance to planar – Proposition 3.13
  • page 25 : bounded treedepth does not imply bounded h-index – Proposition 3.22
  • page 26 : bounded treedepth does not imply bounded distance to perfect – Proposition 3.24
• unknown
  • vertex integrity $k$ upper bounds treedepth by $\mathcal O(k)$ – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
  • distance to stars $k$ upper bounds treedepth by $\mathcal O(k)$ – First, treedepth removes vertices of the modulator, remainder has treedepth $2$
  • treedepth $k$ upper bounds diameter by $f(k)$ – An unbounded diameter implies the class contains paths as subgraphs. Minimum treedepth to embed a path of length $n$ in a treedepth tree is $\log n$.
  • graph class path has unbounded treedepth