shrub-depth $k$ upper bounds linear clique-width by $\mathcal O(k)$ – 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 $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)$. …
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.
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.
