The vertex bound conjecture for critical graphs of tree-depth k
Let be a graph of tree-depth , meaning that is the least number of labels in a vertex ranking of 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 and every proper minor has smaller tree-depth. Vertex bound conjecture. Every critical graph with tree-depth has at most
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
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.