Dvořák–Giannopoulou–Thilikos conjecture on the order of critical graphs

From papers

Let GG be a kk-critical graph, meaning that G\frac{}{}G has tree-depth kk and every proper minor of GG has tree-depth less than kk.

Dvořák–Giannopoulou–Thilikos conjecture. GG has at most

2k12^{k-1}

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

No solutions have been posted yet.