treedepth

abbr: td

tags: vertex removal

equivalent to: d-path-free, treedepth

providers: ISGCI, PACE

Relations

Results

• 2019 Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Mendez
  • 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)$. …
• 2019 The Graph Parameter Hierarchy by Sorge
  • 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$.
• 2010 Comparing 17 graph parameters by Sasák
  • 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 Grad and classes with bounded expansion II. Algorithmic aspects by Nešetřil, Ossona de Mendez
  • d-path-free upper bounds treedepth by a polynomial function
  • treedepth upper bounds d-path-free by an exponential function
• 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$.
• Comparing Graph Parameters by Schröder
  • 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
• 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