Uniqueness and minimal obstructions for tree-depth

DOI10.1016/J.DISC.2015.09.027MaRDI QIDQ898117zbMATH OpenOpenAlexFDO

Authors Michael D. Barrus, John Sinkovic

Publication date 8 December 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph minorstree depthvertex ranking

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83)

Abstract: A k-ranking of a graph G is a labeling of the vertices of G with values from {1,...,k} such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of G is the smallest value of k for which a k-ranking of G exists. The graph G is k-critical if it has tree-depth k and any proper minor of G has smaller tree-depth, and it is 1-unique if for every vertex v in G, there exists an optimal ranking of G in which v is the unique vertex with label 1. We present several classes of graphs that are both k-critical and 1-unique, providing examples that satisfy conjectures on critical graphs discussed in [M.D. Barrus and J. Sinkovic, Uniqueness and minimal obstructions for tree-depth, submitted].

Recommendations

• On 1-uniqueness and dense critical graphs for tree-depth
• Forbidden graphs for tree-depth
• Obstructions for tree-depth
• Arankings of trees
• Further results on minimal rankings

Cites work

• Forbidden graphs for tree-depth
• Grad and classes with bounded expansion. I: Decompositions
• Obstructions for tree-depth
• On-line ranking number for cycles and paths
• Optimal node ranking of trees
• Ordered coloring of grids and related graphs
• Ordered colourings
• Ranking numbers of graphs
• Rankings of Graphs
• Structural sparsity
• Tree-depth, subgraph coloring and homomorphism bounds
• Uniqueness and minimal obstructions for tree-depth

Cited in

(8)

• On 1-uniqueness and dense critical graphs for tree-depth
• A polynomial excluded-minor approximation of treedepth
• Obstructions for tree-depth
• Branch duplication in trees: uniqueness of seeds and enumeration of seeds
• scientific article; zbMATH DE number 5788344 (Why is no real title available?)
• scientific article; zbMATH DE number 5524949 (Why is no real title available?)
• Forbidden graphs for tree-depth
• Uniqueness and minimal obstructions for tree-depth

This page was built for publication: Uniqueness and minimal obstructions for tree-depth

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