The vertex bound conjecture for critical graphs of tree-depth k
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.
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
Sign in to submit a solution.
No solutions have been posted yet.