The vertex bound conjecture for critical graphs of tree-depth k

From papers

Let GG be a graph of tree-depth kk, meaning that kk is the least number of labels in a vertex ranking of GG such that every path joining two vertices with the same label contains a vertex with a higher label. A graph is critical if it has tree-depth kk and every proper minor has smaller tree-depth. Vertex bound conjecture. Every critical graph with tree-depth kk has at most

2k12^{k-1}

vertices. This conjecture concerns the possible size of minor-minimal obstructions at each tree-depth; the supplied source does not state whether the bound has been proved or disproved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Michael D. Barrus and John Sinkovic, “Classes of critical graphs for tree-depth”, arXiv:1502.05277 (2015).

Solutions 0

No solutions have been posted yet.