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

About 11 years old · traced to

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

2k−12^{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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.