On low tree-depth decompositions

DOI10.1007/S00373-015-1569-7zbMATH Open1327.05279arXiv1412.1581OpenAlexW2048377505MaRDI QIDQ897253FDOQ897253

P. Ossona de Mendez, J. Nešetřil

Publication date: 17 December 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1412.1581

zbMATH Keywords

model checkinggraph decompositiontree-depthhomomorphism dualityclasses with bounded expansionlow tree-depth decompositionnowhere dense classes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph searching and a min-max theorem for tree-width
• On the structure of linear graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• On acyclic colorings of planar graphs
• 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
• Tree-depth, subgraph coloring and homomorphism bounds
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Subgraphs and well‐quasi‐ordering
• Color-coding
• Rankings of Graphs
• LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
• Matrix multiplication via arithmetic progressions
• Trivially perfect graphs
• Deciding First-Order Properties of Nowhere Dense Graphs
• When Trees Grow Low: Shrubs and Fast MSO1
• Sparsity. Graphs, structures, and algorithms
• Five-coloring graphs on the torus
• Optimal node ranking of tree in linear time
• On acyclic colorings of graphs on surfaces
• Thue choosability of trees
• Domination problems in nowhere-dense classes of graphs
• Diameter and treewidth in minor-closed graph families
• The complexity of first-order and monadic second-order logic revisited
• Transition graphs and the star-height of regular events
• On nowhere dense graphs
• Linear time low tree-width partitions and algorithmic consequences
• Forbidden graphs for tree-depth
• Homomorphism preservation theorems
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Star arboricity
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Colouring graphs with bounded generalized colouring number
• Orderings on graphs and game coloring number
• Homomorphisms and edge-colourings of planar graphs
• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• Excluding any graph as a minor allows a low tree-width 2-coloring
• How many \(F\)'s are there in \(G\)?
• Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree
• Testing first-order properties for subclasses of sparse graphs
• LIFO-Search on Digraphs: A Searching Game for Cycle-Rank
• On the order of countable graphs
• Enumeration of monadic second-order queries on trees
• Where First-Order and Monadic Second-Order Logic Coincide
• Choosability of P 5-Free Graphs
• On first-order definable colorings
• Model Checking Lower Bounds for Simple Graphs

Cited In (23)

• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
• Regular partitions of gentle graphs
• Critical properties of bipartite permutation graphs
• 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
• Tree densities in sparse graph classes
• Exact distance graphs of product graphs
• Obstructions for bounded shrub-depth and rank-depth
• Coloring and Covering Nowhere Dense Graphs
• Title not available (Why is that?)
• Parameterized analysis and crossing minimization problems
• The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
• Linear colouring of binomial random graphs
• Colouring exact distance graphs of chordal graphs
• Improved Bounds for the Excluded-Minor Approximation of Treedepth
• Compact representation of graphs with bounded bandwidth or treedepth
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• Chromatic numbers of exact distance graphs
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• Diameter estimates for graph associahedra
• Injective coloring of graphs revisited
• The complexity of bicriteria tree-depth

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)