On low tree-depth decompositions
From MaRDI portal
Publication:897253
DOI10.1007/s00373-015-1569-7zbMath1327.05279arXiv1412.1581OpenAlexW2048377505MaRDI QIDQ897253
Patrice Ossona de Mendez, Jaroslav Nešetřil
Publication date: 17 December 2015
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.1581
model checkinggraph decompositionlow tree-depth decompositiontree-depthhomomorphism dualityclasses with bounded expansionnowhere dense classes
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)
Related Items (21)
A polynomial excluded-minor approximation of treedepth ⋮ Tree densities in sparse graph classes ⋮ Chromatic numbers of exact distance graphs ⋮ On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Critical properties of bipartite permutation graphs ⋮ Injective coloring of graphs revisited ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Regular partitions of gentle graphs ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ Unnamed Item ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Exact distance graphs of product graphs ⋮ The complexity of bicriteria tree-depth ⋮ Colouring exact distance graphs of chordal graphs ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ Diameter estimates for graph associahedra ⋮ Hereditary classes of graphs: a parametric approach
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Thue choosability of trees
- Forbidden graphs for tree-depth
- Sparsity. Graphs, structures, and algorithms
- How many \(F\)'s are there in \(G\)?
- LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
- Homomorphisms and edge-colourings of planar graphs
- Matrix multiplication via arithmetic progressions
- Colouring graphs with bounded generalized colouring number
- Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
- Planar orientations with low out-degree and compaction of adjacency matrices
- Star arboricity
- Trivially perfect graphs
- On acyclic colorings of planar graphs
- Graph searching and a min-max theorem for tree-width
- Five-coloring graphs on the torus
- On the order of countable graphs
- Diameter and treewidth in minor-closed graph families
- Optimal node ranking of tree in linear time
- Orderings on graphs and game coloring number
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree
- The complexity of first-order and monadic second-order logic revisited
- On acyclic colorings of graphs on surfaces
- 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
- On nowhere dense graphs
- Tree-depth, subgraph coloring and homomorphism bounds
- Transition graphs and the star-height of regular events
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- When Trees Grow Low: Shrubs and Fast MSO1
- Domination Problems in Nowhere-Dense Classes
- Linear time low tree-width partitions and algorithmic consequences
- Enumeration of monadic second-order queries on trees
- Where First-Order and Monadic Second-Order Logic Coincide
- LIFO-Search on Digraphs: A Searching Game for Cycle-Rank
- Choosability of P 5-Free Graphs
- On first-order definable colorings
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Homomorphism preservation theorems
- Subgraphs and well‐quasi‐ordering
- Color-coding
- Rankings of Graphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Deciding First-Order Properties of Nowhere Dense Graphs
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Model Checking Lower Bounds for Simple Graphs
- Testing first-order properties for subclasses of sparse graphs
- On the structure of linear graphs
This page was built for publication: On low tree-depth decompositions
