On Low Tree-Depth Decompositions
arXiv:1412.1581 · doi:10.1007/s00373-015-1569-7
Abstract
The theory of sparse structures usually uses tree like structures as building blocks. In the context of sparse/dense dichotomy this role is played by graphs with bounded tree depth. In this paper we survey results related to this concept and particularly explain how these graphs are used to decompose and construct more complex graphs and structures. In more technical terms we survey some of the properties and applications of low tree depth decomposition of graphs.
Cited by in corpus (11)
- Exact distance coloring in trees
- Obstructions for bounded shrub-depth and rank-depth
- Tree densities in sparse graph classes
- Injective coloring of graphs revisited
- Diameter estimates for graph associahedra
- Colouring and Covering Nowhere Dense Graphs
- Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space
- Colouring exact distance graphs of chordal graphs
- Chromatic Numbers of Exact Distance Graphs
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Regular partitions of gentle graphs