On the tree-depth of random graphs

DOI10.1016/J.DAM.2012.10.031zbMath1285.05161OpenAlexW1709839140MaRDI QIDQ2442213

Guillem Perarnau, Oriol Serra

Publication date: 2 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.10.031

zbMATH Keywords

random graphstree-widthtree-depth

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Density (toughness, etc.) (05C42)

Related Items (3)

On giant components and treewidth in the layers model ⋮ On the tree-depth and tree-width in heterogeneous random graphs ⋮ On Treewidth and Related Parameters of Random Geometric Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden graphs for tree-depth
• Sparsity. Graphs, structures, and algorithms
• Critical random graphs: Diameter and mixing time
• Treewidth. Computations and approximations
• On the order of countable graphs
• Orderings on graphs and game coloring number
• Coloring with no 2-colored \(P_4\)'s
• Tree-depth, subgraph coloring and homomorphism bounds
• Rank-width of random graphs
• The mixing time of the giant component of a random graph
• The Role of Elimination Trees in Sparse Factorization
• On the Threshold of Having a Linear Treewidth in Random Graphs
• A New Implementation of Sparse Gaussian Elimination
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• On the height of trees

This page was built for publication: On the tree-depth of random graphs