Forbidden graphs for tree-depth

DOI10.1016/j.ejc.2011.09.014zbMath1239.05062OpenAlexW2016741021MaRDI QIDQ412288

Dimitrios M. Thilikos, Zdeněk Dvořák, Archontia C. Giannopoulou

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.09.014

zbMATH Keywords

acyclic obstructions of a graph

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Related Items (20)

A polynomial excluded-minor approximation of treedepth ⋮ Characterizing width two for variants of treewidth ⋮ Sparse obstructions for minor-covering parameters ⋮ Forbidding Kuratowski Graphs as Immersions ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ On low tree-depth decompositions ⋮ Uniqueness and minimal obstructions for tree-depth ⋮ On the tree-depth of random graphs ⋮ Characterizing graphs of small carving-width ⋮ On 1-uniqueness and dense critical graphs for tree-depth ⋮ Unnamed Item ⋮ Minor obstructions for apex-pseudoforests ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ The complexity of bicriteria tree-depth ⋮ FPT is characterized by useful obstruction sets ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ Minor-obstructions for apex sub-unicyclic graphs ⋮ On the tree-depth and tree-width in heterogeneous random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Algorithms and obstructions for linear-width and related search parameters
• Optimal edge ranking of trees in polynomial time
• Ordered colourings
• 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
• Outerplanar Obstructions for the Feedback Vertex Set
• Obstructions for Tree-depth
• Linear time low tree-width partitions and algorithmic consequences
• The Role of Elimination Trees in Sparse Factorization
• Rankings of Graphs

This page was built for publication: Forbidden graphs for tree-depth