treedepth

• 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$.
• SchroderThesis
  • page 11 : treedepth upper bounds diameter by an exponential function – 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
• Sorge2019
  • page 11 : treedepth upper bounds pathwidth by a linear function – Lemma 4.27. The treedepth $t$ strictly upper bounds the pathwidth $p$. We have $p \le t$.
• gradnesetril2008
  • d-path-free upper bounds treedepth by a polynomial function
  • treedepth upper bounds d-path-free by an exponential function
• Ganian2019
  • treedepth upper bounds shrub-depth by a linear function – Proposition 3.2. If $G$ is of tree-depth $d$, then $G \in \mathcal{TM}_{2^d}(d)$. …
• unknown source
  • vertex integrity upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
  • distance to stars upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, remainder has treedepth $2$
  • graph class path has unbounded treedepth
• 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$.