shrub-depth

Relations

Other		Relation from	Relation to
acyclic chromatic number	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	magenta■	exclusion	unknown to HOPS
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
boxicity	magenta■	exclusion	unknown to HOPS
branch width	cyan■	unknown to HOPS	exclusion
c-closure	blue■	exclusion	exclusion
carving-width	cyan■	unknown to HOPS	exclusion
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	cyan■	unknown to HOPS	exclusion
cograph	cyan■	unknown to HOPS	exclusion
complete	green■	upper bound	exclusion
connected	blue■	unbounded	exclusion
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-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
disconnected	cyan■	unknown to HOPS	exclusion
disjoint cycles	cyan■	unknown to HOPS	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	cyan■	unknown to HOPS	exclusion
distance to cograph	cyan■	unknown to HOPS	exclusion
distance to complete	green■	upper bound	exclusion
distance to disconnected	blue■	exclusion	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
edge clique cover number	green■	upper bound	exclusion
edge connectivity	blue■	exclusion	exclusion
edgeless	green■	upper bound	exclusion
feedback edge set	cyan■	unknown to HOPS	exclusion
feedback vertex set	cyan■	unknown to HOPS	exclusion
forest	cyan■	unknown to HOPS	exclusion
genus	blue■	exclusion	exclusion
girth	magenta■	exclusion	unknown to HOPS
grid	blue■	unbounded	exclusion
h-index	blue■	exclusion	exclusion
inf-flip-width	red■	exclusion	upper bound
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
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
neighborhood diversity	green■	upper bound	exclusion
NLC-width	red■	exclusion	upper bound
NLCT-width	orange■	unknown to HOPS	upper bound
odd cycle transversal	blue■	exclusion	exclusion
outerplanar	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-r flip-width	red■	exclusion	upper bound
rank-width	red■	exclusion	upper bound
shrub-depth	yellow■	equal	equal
sim-width	red■	exclusion	upper bound
size	green■	upper bound	exclusion
star	green■	upper bound	exclusion
stars	green■	upper bound	exclusion
topological bandwidth	cyan■	unknown to HOPS	exclusion
tree	cyan■	unknown to HOPS	exclusion
tree-independence number	gray■	unknown to HOPS	unknown to HOPS
treedepth	green■	upper bound	exclusion
treelength	magenta■	exclusion	unknown to HOPS
treewidth	cyan■	unknown to HOPS	exclusion
twin-cover number	green■	upper bound	exclusion
twin-width	red■	exclusion	upper bound
vertex connectivity	blue■	exclusion	exclusion
vertex cover	green■	upper bound	exclusion
vertex integrity	green■	upper bound	exclusion

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.
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.
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.