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
- 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₄-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?
- 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?)
- 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
(34)- Chromatic numbers of exact distance graphs
- Obstructions for bounded shrub-depth and rank-depth
- Diameter estimates for graph associahedra
- Hereditary classes of graphs: a parametric approach
- A polynomial excluded-minor approximation of treedepth
- On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
- Parameterized analysis and crossing minimization problems
- Regular partitions of gentle graphs
- Exact distance graphs of product graphs
- Colouring exact distance graphs of chordal graphs
- Compact representation of graphs with bounded bandwidth or treedepth
- Injective coloring of graphs revisited
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
- Coloring and covering nowhere dense graphs
- Improved bounds for the excluded-minor approximation of treedepth
- Tree densities in sparse graph classes
- Improved bounds for the excluded-minor approximation of treedepth
- Dynamic low-stretch trees via dynamic low-diameter decompositions
- The complexity of bicriteria tree-depth
- The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Critical properties of bipartite permutation graphs
- Linear colouring of binomial random graphs
- Treelike decompositions for transductions of sparse graphs
- Graph problems and monotone classes
- An improved kernelization algorithm for trivially perfect editing
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- Computing treedepth in polynomial space and linear FPT time
- Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
- Decomposition horizons: from graph sparsity to model-theoretic dividing lines (extended abstract)
- Linear versus centred colouring via pseudogrids
- Structural parameterizations of k-planarity
- Structural parameterizations of \(k\)-planarity
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)
