Dvořák–Giannopoulou–Thilikos conjecture on the order of critical graphs
Dvořák–Giannopoulou–Thilikos conjecture on the order of critical graphs
Let be a -critical graph, meaning that has tree-depth and every proper minor of has tree-depth less than .
Dvořák–Giannopoulou–Thilikos conjecture. has at most
vertices.
This conjecture concerns the maximum order of graphs that are minor-critical for tree-depth. It is attributed in the source to Dvořák, Giannopoulou, and Thilikos and remains open in full generality.
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, “On 1-uniqueness and dense critical graphs for tree-depth”, arXiv:1704.07311 (2017).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.