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