treedepth

abbr: td

Definitions:

Treedepth of a graph is height of an auxiliary rooted forest over graph’s vertices such that all edges of the graph have ancestor-descendant relationship within the tree.
For a graph treedepth is 1 if the graph is a single vertex. Otherwise, it is the minimum value obtained by removing some vertex and taking maximum over treedepths of each connected component.

Relations

Other		Relation from	Relation to
acyclic chromatic number	red■	exclusion	upper bound
arboricity	red■	exclusion	upper bound
average degree	red■	exclusion	upper bound
average distance	red■	exclusion	upper bound
bandwidth	blue■	exclusion	exclusion
bipartite	blue■	unbounded	exclusion
bipartite number	red■	exclusion	upper bound
bisection bandwidth	blue■	exclusion	exclusion
block	blue■	unbounded	exclusion
book thickness	red■	exclusion	upper bound
boolean width	red■	exclusion	upper bound
bounded components	green■	upper bound	exclusion
boxicity	red■	exclusion	upper bound
branch width	red■	exclusion	upper bound
c-closure	blue■	exclusion	exclusion
carving-width	blue■	exclusion	exclusion
chordal	blue■	unbounded	exclusion
chordality	red■	exclusion	upper bound
chromatic number	red■	exclusion	upper bound
clique cover number	blue■	exclusion	exclusion
clique-tree-width	red■	exclusion	upper bound
clique-width	red■	exclusion	upper bound
cluster	blue■	unbounded	exclusion
co-cluster	blue■	unbounded	exclusion
cograph	blue■	unbounded	exclusion
complete	blue■	unbounded	exclusion
connected	blue■	unbounded	exclusion
contraction complexity	blue■	exclusion	exclusion
cutwidth	blue■	exclusion	exclusion
cycle	blue■	unbounded	exclusion
cycles	blue■	unbounded	exclusion
d-path-free	yellow■	upper bound	upper bound
degeneracy	red■	exclusion	upper bound
degree treewidth	blue■	exclusion	exclusion
diameter	red■	exclusion	upper bound
diameter+max degree	green■	upper bound	exclusion
disconnected	gray■	unknown to HOPS	unknown to HOPS
disjoint cycles	blue■	unbounded	exclusion
distance to bipartite	blue■	exclusion	exclusion
distance to block	blue■	exclusion	exclusion
distance to bounded components	green■	upper bound	exclusion
distance to chordal	blue■	exclusion	exclusion
distance to cluster	blue■	exclusion	exclusion
distance to co-cluster	blue■	exclusion	exclusion
distance to cograph	blue■	exclusion	exclusion
distance to complete	blue■	exclusion	exclusion
distance to disconnected	red■	exclusion	upper bound
distance to edgeless	green■	upper bound	exclusion
distance to forest	blue■	exclusion	exclusion
distance to interval	blue■	exclusion	exclusion
distance to linear forest	blue■	exclusion	exclusion
distance to maximum degree	blue■	exclusion	exclusion
distance to outerplanar	blue■	exclusion	exclusion
distance to perfect	blue■	exclusion	exclusion
distance to planar	blue■	exclusion	exclusion
distance to stars	green■	upper bound	exclusion
domatic number	red■	exclusion	upper bound
domination number	blue■	exclusion	exclusion
edge clique cover number	blue■	exclusion	exclusion
edge connectivity	red■	exclusion	upper bound
edgeless	green■	upper bound	exclusion
feedback edge set	blue■	exclusion	exclusion
feedback vertex set	blue■	exclusion	exclusion
forest	blue■	unbounded	exclusion
genus	blue■	exclusion	exclusion
girth	red■	exclusion	upper bound
grid	blue■	unbounded	exclusion
h-index	blue■	exclusion	exclusion
inf-flip-width	red■	exclusion	upper bound
interval	blue■	unbounded	exclusion
iterated type partitions	magenta■	exclusion	unknown to HOPS
linear clique-width	red■	exclusion	upper bound
linear forest	blue■	unbounded	exclusion
linear NLC-width	red■	exclusion	upper bound
linear rank-width	red■	exclusion	upper bound
maximum clique	red■	exclusion	upper bound
maximum degree	blue■	exclusion	exclusion
maximum independent set	blue■	exclusion	exclusion
maximum induced matching	magenta■	exclusion	unknown to HOPS
maximum leaf number	blue■	exclusion	exclusion
maximum matching	green■	upper bound	exclusion
maximum matching on bipartite graphs	green■	upper bound	exclusion
mim-width	red■	exclusion	upper bound
minimum degree	red■	exclusion	upper bound
mm-width	red■	exclusion	upper bound
modular-width	magenta■	exclusion	unknown to HOPS
module-width	red■	exclusion	upper bound
neighborhood diversity	blue■	exclusion	exclusion
NLC-width	red■	exclusion	upper bound
NLCT-width	red■	exclusion	upper bound
odd cycle transversal	blue■	exclusion	exclusion
outerplanar	blue■	unbounded	exclusion
path	blue■	unbounded	exclusion
pathwidth	red■	exclusion	upper bound
pathwidth+maxdegree	blue■	exclusion	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	red■	exclusion	upper bound
sim-width	red■	exclusion	upper bound
size	green■	upper bound	exclusion
star	green■	upper bound	exclusion
stars	green■	upper bound	exclusion
topological bandwidth	blue■	exclusion	exclusion
tree	blue■	unbounded	exclusion
tree-independence number	red■	exclusion	upper bound
treedepth	yellow■	equal	equal
treelength	red■	exclusion	upper bound
treewidth	red■	exclusion	upper bound
twin-cover number	blue■	exclusion	exclusion
twin-width	red■	exclusion	upper bound
vertex connectivity	red■	exclusion	upper bound
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
- 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)$. …
2019 The Graph Parameter Hierarchy by Sorge
- page 11 : treedepth upper bounds pathwidth by a linear function – Lemma 4.27. The treedepth $t$ strictly upper bounds the pathwidth $p$. We have $p \le t$.
2010 Comparing 17 graph parameters by Sasák
- page 32 : graph class grid has unbounded treedepth – Corollary 2.24 Tree-depth of a grid is at least $\lceil \log_2(n+1)\rceil$.
2008 Grad and classes with bounded expansion II. Algorithmic aspects by Nešetřil, Ossona de Mendez
- d-path-free upper bounds treedepth by a polynomial function
- treedepth upper bounds d-path-free by an exponential function
Comparing Graph Parameters by Schröder
- page 11 : treedepth upper bounds diameter by an exponential function – Proposition 3.1
- page 21 : bounded treedepth does not imply bounded distance to planar – Proposition 3.13
- page 25 : bounded treedepth does not imply bounded h-index – Proposition 3.22
- page 26 : bounded treedepth does not imply bounded distance to perfect – Proposition 3.24
assumed
- treedepth is equivalent to treedepth – assumed
unknown source
- vertex integrity upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
- distance to stars upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, remainder has treedepth $2$
- graph class path has unbounded treedepth