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

About 9 years old · traced to

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

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

References

Primary source

Michael D. Barrus and John Sinkovic, “On 1-uniqueness and dense critical graphs for tree-depth”, arXiv:1704.07311 (2017).

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.