On low tree-depth decompositions
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6678444 (Why is no real title available?)
- scientific article; zbMATH DE number 1003278 (Why is no real title available?)
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 139776 (Why is no real title available?)
- scientific article; zbMATH DE number 3563170 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 910922 (Why is no real title available?)
- scientific article; zbMATH DE number 1414315 (Why is no real title available?)
- scientific article; zbMATH DE number 2209736 (Why is no real title available?)
- Choosability of P 5-Free Graphs
- Color-coding
- Colouring graphs with bounded generalized colouring number
- Diameter and treewidth in minor-closed graph families
- Domination problems in nowhere-dense classes of graphs
- Enumeration of monadic second-order queries on trees
- Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Five-coloring graphs on the torus
- Forbidden graphs for tree-depth
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- Graph searching and a min-max theorem for tree-width
- Homomorphism preservation theorems
- Homomorphisms and edge-colourings of planar graphs
- Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
- How many \(F\)'s are there in \(G\)?
- LIFO-search on digraphs: a searching game for cycle-rank
- LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
- Linear time low tree-width partitions and algorithmic consequences
- Matrix multiplication via arithmetic progressions
- Model checking lower bounds for simple graphs
- On acyclic colorings of graphs on surfaces
- On acyclic colorings of planar graphs
- On first-order definable colorings
- On nowhere dense graphs
- On the order of countable graphs
- On the structure of linear graphs
- Optimal node ranking of tree in linear time
- Orderings on graphs and game coloring number
- Planar orientations with low out-degree and compaction of adjacency matrices
- Rankings of Graphs
- Sparsity. Graphs, structures, and algorithms
- Star arboricity
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Subgraphs and well‐quasi‐ordering
- Testing first-order properties for subclasses of sparse graphs
- The complexity of first-order and monadic second-order logic revisited
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Thue choosability of trees
- Transition graphs and the star-height of regular events
- Tree-depth, subgraph coloring and homomorphism bounds
- Trivially perfect graphs
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
- Where first-order and monadic second-order logic coincide
Cited in
(25)- Diameter estimates for graph associahedra
- From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
- Treelike decompositions for transductions of sparse graphs
- On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
- Hereditary classes of graphs: a parametric approach
- Chromatic numbers of exact distance graphs
- A polynomial excluded-minor approximation of treedepth
- Obstructions for bounded shrub-depth and rank-depth
- Tree densities in sparse graph classes
- The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
- Injective coloring of graphs revisited
- Linear colouring of binomial random graphs
- Critical properties of bipartite permutation graphs
- scientific article; zbMATH DE number 7525471 (Why is no real title available?)
- Compact representation of graphs with bounded bandwidth or treedepth
- Dynamic low-stretch trees via dynamic low-diameter decompositions
- Parameterized analysis and crossing minimization problems
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- The complexity of bicriteria tree-depth
- Improved bounds for the excluded-minor approximation of treedepth
- Coloring and covering nowhere dense graphs
- Colouring exact distance graphs of chordal graphs
- Regular partitions of gentle graphs
- Exact distance graphs of product graphs
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
This page was built for publication: On low tree-depth decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897253)
