treedepth

abbr: td

tags: vertex removal

functionally equivalent to: weak inf-coloring number, d-path-free

providers: ISGCI, PACE

Definitions:

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

OtherRelation fromRelation to
acyclic chromatic numberredexclusionupper bound
admissibilityredexclusionupper bound
arboricityredexclusionupper bound
average degreeredexclusionupper bound
average distanceredexclusionupper bound
bandwidthcyanunknown to HOPSexclusion
bipartiteblueunboundedexclusion
bipartite numberblueexclusionexclusion
bisection bandwidthblueexclusionexclusion
blockblueunboundedexclusion
book thicknessredexclusionupper bound
boolean widthredexclusionupper bound
bounded componentsgreenupper boundexclusion
bounded expansionredexclusionupper bound
boxicityredexclusionupper bound
branch widthredexclusionupper bound
c-closureblueexclusionexclusion
carving-widthblueexclusionexclusion
chi-boundedredexclusionupper bound
chordalblueunboundedexclusion
chordalityredexclusionupper bound
chromatic numberredexclusionupper bound
clique cover numberblueexclusionexclusion
clique-tree-widthredexclusionupper bound
clique-widthredexclusionupper bound
clusterblueunboundedexclusion
co-clusterblueunboundedexclusion
cographblueunboundedexclusion
completeblueunboundedexclusion
connectedblueexclusionavoids
contraction complexityblueexclusionexclusion
cutwidthblueexclusionexclusion
cyclecyanunknown to HOPSexclusion
cyclescyanunknown to HOPSexclusion
d-admissibilityredexclusionupper bound
d-path-freeyellowupper boundupper bound
degeneracyredexclusionupper bound
degree treewidthblueexclusionexclusion
diameterredexclusionupper bound
diameter+max degreegreenupper boundexclusion
distance to bipartiteblueexclusionexclusion
distance to blockblueexclusionexclusion
distance to bounded componentsgreenupper boundexclusion
distance to chordalblueexclusionexclusion
distance to clusterblueexclusionexclusion
distance to co-clusterblueexclusionexclusion
distance to cographblueexclusionexclusion
distance to completeblueexclusionexclusion
distance to edgelessgreenupper boundexclusion
distance to forestblueexclusionexclusion
distance to intervalblueexclusionexclusion
distance to linear forestblueexclusionexclusion
distance to maximum degreeblueexclusionexclusion
distance to outerplanarblueexclusionexclusion
distance to perfectblueexclusionexclusion
distance to planarblueexclusionexclusion
distance to starsgreenupper boundexclusion
domatic numberredexclusionupper bound
domination numberblueexclusionexclusion
domino treewidthblueexclusionexclusion
edge clique cover numberblueexclusionexclusion
edge connectivityredexclusionupper bound
edge-cut widthmagentaexclusionunknown to HOPS
edge-treewidthmagentaexclusionunknown to HOPS
edgelessgreenupper boundavoids
excluded minormagentaexclusionunknown to HOPS
excluded planar minorgrayunknown to HOPSunknown to HOPS
excluded top-minorredexclusionupper bound
feedback edge setblueexclusionexclusion
feedback vertex setblueexclusionexclusion
flip-widthredexclusionupper bound
forestblueunboundedexclusion
genusblueexclusionexclusion
gridblueunboundedexclusion
h-indexblueexclusionexclusion
intervalblueunboundedexclusion
iterated type partitionsmagentaexclusionunknown to HOPS
linear clique-widthredexclusionupper bound
linear forestblueunboundedexclusion
linear NLC-widthredexclusionupper bound
linear rank-widthredexclusionupper bound
maximum cliqueredexclusionupper bound
maximum degreeblueexclusionexclusion
maximum independent setblueexclusionexclusion
maximum induced matchingmagentaexclusionunknown to HOPS
maximum leaf numbercyanunknown to HOPSexclusion
maximum matchinggreenupper boundexclusion
maximum matching on bipartite graphsgreenupper boundexclusion
merge-widthredexclusionupper bound
mim-widthredexclusionupper bound
minimum degreeredexclusionupper bound
mm-widthredexclusionupper bound
modular-widthmagentaexclusionunknown to HOPS
module-widthredexclusionupper bound
monadically dependentredexclusionupper bound
monadically stableredexclusionupper bound
neighborhood diversityblueexclusionexclusion
NLC-widthredexclusionupper bound
NLCT-widthredexclusionupper bound
nowhere denseredexclusionupper bound
odd cycle transversalblueexclusionexclusion
outerplanarcyanunknown to HOPSexclusion
overlap treewidthmagentaexclusionunknown to HOPS
pathblueunboundedexclusion
pathwidthredexclusionupper bound
pathwidth+maxdegreeblueexclusionexclusion
perfectblueunboundedexclusion
planarblueunboundedexclusion
radius-inf flip-widthredexclusionupper bound
radius-r flip-widthredexclusionupper bound
rank-widthredexclusionupper bound
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthredexclusionupper bound
sim-widthredexclusionupper bound
sizegreenupper boundexclusion
slim tree-cut widthmagentaexclusionunknown to HOPS
sparse twin-widthredexclusionupper bound
stargreenupper boundexclusion
starsgreenupper boundexclusion
strong coloring numberredexclusionupper bound
strong d-coloring numberredexclusionupper bound
strong inf-coloring numberredexclusionupper bound
topological bandwidthcyanunknown to HOPSexclusion
treeblueunboundedexclusion
tree-cut widthmagentaexclusionunknown to HOPS
tree-independence numberredexclusionupper bound
tree-partition-widthmagentaexclusionunknown to HOPS
treebandwidthmagentaexclusionunknown to HOPS
treedepthyellowequalequal
treelengthredexclusionupper bound
treespanblueexclusionexclusion
treewidthredexclusionupper bound
twin-cover numberblueexclusionexclusion
twin-widthredexclusionupper bound
vertex connectivitygrayunknown to HOPSunknown to HOPS
vertex covergreenupper boundexclusion
vertex integritygreenupper boundexclusion
weak coloring numberredexclusionupper bound
weak d-coloring numberredexclusionupper bound
weak inf-coloring numberyellowupper boundupper bound
weakly sparseredexclusionupper bound
weakly sparse and merge widthredexclusionupper bound

Results