shrub-depth

equivalent to: shrub-depth

Relations

Results

• 2019 Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Mendez
  • shrub-depth upper bounds linear clique-width by a linear function – Proposition 3.4. Let $\mathcal G$ be a graph class and $d$ an integer. Then: … b) If $\mathcal G$ is of bounded shrub-depth, then $\mathcal G$ is of bounded linear clique-width.
  • neighborhood diversity upper bounds shrub-depth by a constant – $\mathcal{TM}_m(1)$ is exactly the class of graphs of neighborhood diversity at most $m$.
  • 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)$. …
• 2015 Improving Vertex Cover as a Graph Parameter by Ganian
  • page 20 : twin-cover number upper bounds shrub-depth by a constant – Let $\mathcal H_k$ be the class of graphs of twin-cover $k$. Then $\mathcal H_k \subseteq \mathcal{TM}_{2^k+k}(2)$ and a tree-model of any $G \in \mathcal H_k$ may be constructed in single-exponential FPT time.
• 2013 Parameterized Algorithms for Modular-Width by Gajarský, Lampis, Ordyniak
  • page 8 : bounded modular-width does not imply bounded shrub-depth – Theorem 4. There are classes of graphs with unbounded modular-width and bounded shrub-depth and vice versa.
  • page 8 : bounded shrub-depth does not imply bounded modular-width – Theorem 4. There are classes of graphs with unbounded modular-width and bounded shrub-depth and vice versa.
• https://www.fi.muni.cz/~hlineny/papers/shrubdepth-warw18-slipp.pdf
  • page 7 : shrub-depth – Tree-model of $m$ colors and depth $d$: a rooted tree $T$ of height $d$, leaves are the vertices of $G$, each leaf has one of $m$ colors, an associated signature determining the edge set of $G$ as follows: for $i=1,2,\dots,d$, let $u$ and $v$ be leaves with the least common ancestor at height $i$ in $T$, then $uv \in E(G)$ iff the color pair of $u,v$ is in the signature at height $i$.
  • page 9 : neighborhood diversity upper bounds shrub-depth by a constant – Shrub-depth 1: e.g., cliques, stars, \dots, gen. BND – bounded neighborhood diversity.