Ganian2019

https://www.doi.org/10.48550/ARXIV.1707.00359

@article{Ganian2019,
archiveprefix = {arXiv},
author = {Robert Ganian and Petr Hliněný and Jaroslav Nešetřil and Jan Obdržálek and Patrice Ossona de Mendez},
copyright = {Creative Commons Attribution 4.0 International},
doi = {10.48550/ARXIV.1707.00359},
eprint = {1707.00359},
month = {January},
publisher = {arXiv},
title = {Shrub-depth: Capturing Height of Dense Graphs},
year = {2019},
}

• 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)$. …