Obstructions for tree-depth

DOI10.1016/J.ENDM.2009.07.041zbMATH Open1273.05212OpenAlexW1999614709MaRDI QIDQ2851471FDOQ2851471

Authors: Archontia C. Giannopoulou, Dimitrios M. Thilikos 

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.07.041

Recommendations

• Forbidden graphs for tree-depth
• Uniqueness and minimal obstructions for tree-depth
• Obstructions for bounded shrub-depth and rank-depth
• Tree-depth, subgraph coloring and homomorphism bounds
• The Structure and Number of Obstructions to Treewidth

zbMATH Keywords

graph minorsobstructionsgraph enumerationtree depthvertex rankings

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph minors (05C83)

Cites Work

• Graph minors. XX: Wagner's conjecture
• 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
• Rankings of Graphs
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Algorithms and obstructions for linear-width and related search parameters
• Ordered colourings
• The Role of Elimination Trees in Sparse Factorization
• Title not available (Why is that?)
• Optimal edge ranking of trees in polynomial time
• Linear time low tree-width partitions and algorithmic consequences
• Title not available (Why is that?)

Cited In (5)

• Outerplanar obstructions for a feedback vertex set
• Graph minors and parameterized algorithm design
• Tree containment and degree conditions
• Uniqueness and minimal obstructions for tree-depth
• Forbidden graphs for tree-depth

This page was built for publication: Obstructions for tree-depth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851471)