shrub-depth

Definition: see https://www.fi.muni.cz/~hlineny/papers/shrubdepth-warw18-slipp.pdf

Relations

Other		Relation from	Relation to
acyclic chromatic number	blue■	exclusion	exclusion
admissibility	blue■	exclusion	exclusion
arboricity	blue■	exclusion	exclusion
average degree	blue■	exclusion	exclusion
average distance	magenta■	exclusion	unknown to HOPS
bandwidth	cyan■	unknown to HOPS	exclusion
bipartite	blue■	unbounded	exclusion
bipartite number	blue■	exclusion	exclusion
bisection bandwidth	blue■	exclusion	exclusion
block	cyan■	unknown to HOPS	exclusion
book thickness	blue■	exclusion	exclusion
boolean width	red■	exclusion	upper bound
bounded components	green■	upper bound	exclusion
bounded expansion	blue■	exclusion	avoids
boxicity	blue■	exclusion	exclusion
branch width	cyan■	unknown to HOPS	exclusion
c-closure	blue■	exclusion	exclusion
carving-width	cyan■	unknown to HOPS	exclusion
chi-bounded	red■	exclusion	upper bound
chordal	cyan■	unknown to HOPS	exclusion
chordality	magenta■	exclusion	unknown to HOPS
chromatic number	blue■	exclusion	exclusion
clique cover number	blue■	exclusion	exclusion
clique-tree-width	orange■	unknown to HOPS	upper bound
clique-width	red■	exclusion	upper bound
cluster	green■	upper bound	exclusion
co-cluster	green■	upper bound	exclusion
cograph	cyan■	unknown to HOPS	exclusion
complete	green■	upper bound	exclusion
connected	blue■	exclusion	avoids
contraction complexity	cyan■	unknown to HOPS	exclusion
cutwidth	cyan■	unknown to HOPS	exclusion
cycle	cyan■	unknown to HOPS	exclusion
cycles	cyan■	unknown to HOPS	exclusion
d-admissibility	magenta■	exclusion	unknown to HOPS
d-path-free	green■	upper bound	exclusion
degeneracy	blue■	exclusion	exclusion
degree treewidth	cyan■	unknown to HOPS	exclusion
diameter	magenta■	exclusion	unknown to HOPS
diameter+max degree	green■	upper bound	exclusion
distance to bipartite	blue■	exclusion	exclusion
distance to block	cyan■	unknown to HOPS	exclusion
distance to bounded components	green■	upper bound	exclusion
distance to chordal	blue■	exclusion	exclusion
distance to cluster	green■	upper bound	exclusion
distance to co-cluster	green■	upper bound	exclusion
distance to cograph	cyan■	unknown to HOPS	exclusion
distance to complete	green■	upper bound	exclusion
distance to edgeless	green■	upper bound	exclusion
distance to forest	cyan■	unknown to HOPS	exclusion
distance to interval	blue■	exclusion	exclusion
distance to linear forest	cyan■	unknown to HOPS	exclusion
distance to maximum degree	blue■	exclusion	exclusion
distance to outerplanar	cyan■	unknown to HOPS	exclusion
distance to perfect	blue■	exclusion	exclusion
distance to planar	blue■	exclusion	exclusion
distance to stars	green■	upper bound	exclusion
domatic number	blue■	exclusion	exclusion
domination number	blue■	exclusion	exclusion
domino treewidth	cyan■	unknown to HOPS	exclusion
edge clique cover number	green■	upper bound	exclusion
edge connectivity	blue■	exclusion	exclusion
edge-cut width	cyan■	unknown to HOPS	exclusion
edge-treewidth	cyan■	unknown to HOPS	exclusion
edgeless	green■	upper bound	avoids
excluded minor	blue■	exclusion	avoids
excluded planar minor	cyan■	unknown to HOPS	avoids
excluded top-minor	blue■	exclusion	avoids
feedback edge set	cyan■	unknown to HOPS	exclusion
feedback vertex set	cyan■	unknown to HOPS	exclusion
flip-width	red■	exclusion	upper bound
forest	cyan■	unknown to HOPS	exclusion
genus	blue■	exclusion	exclusion
grid	blue■	unbounded	exclusion
h-index	blue■	exclusion	exclusion
interval	cyan■	unknown to HOPS	exclusion
iterated type partitions	cyan■	unknown to HOPS	exclusion
linear clique-width	orange■	unknown to HOPS	upper bound
linear forest	cyan■	unknown to HOPS	exclusion
linear NLC-width	orange■	unknown to HOPS	upper bound
linear rank-width	orange■	unknown to HOPS	upper bound
maximum clique	blue■	exclusion	exclusion
maximum degree	blue■	exclusion	exclusion
maximum independent set	blue■	exclusion	exclusion
maximum induced matching	magenta■	exclusion	unknown to HOPS
maximum leaf number	cyan■	unknown to HOPS	exclusion
maximum matching	green■	upper bound	exclusion
maximum matching on bipartite graphs	green■	upper bound	exclusion
merge-width	red■	exclusion	upper bound
mim-width	red■	exclusion	upper bound
minimum degree	blue■	exclusion	exclusion
mm-width	cyan■	unknown to HOPS	exclusion
modular-width	blue■	exclusion	exclusion
module-width	red■	exclusion	upper bound
monadically dependent	red■	exclusion	upper bound
monadically stable	magenta■	exclusion	unknown to HOPS
neighborhood diversity	green■	upper bound	exclusion
NLC-width	red■	exclusion	upper bound
NLCT-width	orange■	unknown to HOPS	upper bound
nowhere dense	magenta■	exclusion	unknown to HOPS
odd cycle transversal	blue■	exclusion	exclusion
outerplanar	cyan■	unknown to HOPS	exclusion
overlap treewidth	cyan■	unknown to HOPS	exclusion
path	cyan■	unknown to HOPS	exclusion
pathwidth	cyan■	unknown to HOPS	exclusion
pathwidth+maxdegree	cyan■	unknown to HOPS	exclusion
perfect	blue■	unbounded	exclusion
planar	blue■	unbounded	exclusion
radius-inf flip-width	red■	exclusion	upper bound
radius-r flip-width	red■	exclusion	upper bound
rank-width	red■	exclusion	upper bound
series-parallel	gray■	unknown to HOPS	unknown to HOPS
shrub-depth	yellow■	equal	equal
sim-width	red■	exclusion	upper bound
size	green■	upper bound	exclusion
slim tree-cut width	cyan■	unknown to HOPS	exclusion
sparse twin-width	blue■	exclusion	exclusion
star	green■	upper bound	exclusion
stars	green■	upper bound	exclusion
strong coloring number	blue■	exclusion	exclusion
strong d-coloring number	magenta■	exclusion	unknown to HOPS
strong inf-coloring number	cyan■	unknown to HOPS	exclusion
topological bandwidth	cyan■	unknown to HOPS	exclusion
tree	cyan■	unknown to HOPS	exclusion
tree-cut width	cyan■	unknown to HOPS	exclusion
tree-independence number	magenta■	exclusion	unknown to HOPS
tree-partition-width	cyan■	unknown to HOPS	exclusion
treebandwidth	cyan■	unknown to HOPS	exclusion
treedepth	green■	upper bound	exclusion
treelength	magenta■	exclusion	unknown to HOPS
treespan	cyan■	unknown to HOPS	exclusion
treewidth	cyan■	unknown to HOPS	exclusion
twin-cover number	green■	upper bound	exclusion
twin-width	red■	exclusion	upper bound
vertex connectivity	gray■	unknown to HOPS	unknown to HOPS
vertex cover	green■	upper bound	exclusion
vertex integrity	green■	upper bound	exclusion
weak coloring number	blue■	exclusion	exclusion
weak d-coloring number	magenta■	exclusion	unknown to HOPS
weak inf-coloring number	green■	upper bound	exclusion
weakly sparse	magenta■	exclusion	unknown to HOPS
weakly sparse and merge width	blue■	exclusion	exclusion

Results

2019 Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Ossona de 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 : graph classes with bounded modular-width are not bounded shrub-depth – Theorem 4. There are classes of graphs with unbounded modular-width and bounded shrub-depth and vice versa.
- page 8 : graph classes with bounded shrub-depth are not bounded modular-width – Theorem 4. There are classes of graphs with unbounded modular-width and bounded shrub-depth and vice versa.
assumed
- shrub-depth is equivalent to shrub-depth – assumed
unknown source
- distance to cluster upper bounds shrub-depth by a constant – J. Pokorný, personal communication: Assume the class of constant dtc we want to show it has constant sd as well. For each clique connect them in a star in the tree model T. Each vertex in the modulator connect to their own vertex in T. Add a root that is in distance 2 to all leaves. Now give each vertex in the modulator a unique colour. Each other vertex that is not in the modulator has as it’s colour the set of neighbours from the modulator. In total there are $2^{dtc} + dtc$ colours that is a constant.
- distance to co-cluster upper bounds shrub-depth by a constant – M. Dvořák, personal communication: The proof essentially follows the Reason why there’s an arrow from cvdn (distance to cluster) to sd. Or note that distance to co-cluster is just complement of distance to cluster. And shrub-depth is closed under complemenetation.
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$.