Branch-depth: generalizing tree-depth of graphs

DOI10.1016/j.ejc.2020.103186zbMath1458.05042arXiv1903.11988OpenAlexW2923540477MaRDI QIDQ2225398

O-joung Kwon, Matt DeVos, Sang-il Oum

Publication date: 8 February 2021

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

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

zbMATH Keywords

matroidsbounded tree-depthbranch-depth of a connectivity function

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (7)

Graphs of bounded depth‐2 rank‐brittleness ⋮ Critical properties of bipartite permutation graphs ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Obstructions for Bounded Branch-depth in Matroids ⋮ On low rank-width colorings ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tree-depth and vertex-minors
• First order convergence of matroids
• Sparsity. Graphs, structures, and algorithms
• Asymptotically optimal induced universal graphs
• Matroid tree-width
• Graph minors. X: Obstructions to tree-decomposition
• Unavoidable minors of graphs of large type
• Branch-width and well-quasi-ordering in matroids and graphs.
• On infinite antichains of matroids
• On tree-partitions of graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The branchwidth of graphs and their cycle matroids
• A sharp bound on the size of a connected matroid
• Large Wk- or K3,t-Minors in 3-Connected Graphs
• Subgraphs and well‐quasi‐ordering
• Finding branch-decompositions of matroids, hypergraphs, and more
• Rank‐width is less than or equal to branch‐width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Matroid T‐Connectivity
• Ordering by Divisibility in Abstract Algebras
• Some Theorems on Abstract Graphs
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Branch-depth: generalizing tree-depth of graphs