The maximum-degree conjecture for critical graphs of tree-depth

Let GG be a critical graph with tree-depth kk, meaning that GG has tree-depth kk and every proper minor of GG has smaller tree-depth. The maximum-degree conjecture. The maximum degree of GG is at most

k1.k-1.

The paper presents this as one of two conjectures motivating its construction of critical and 1-unique graph classes; no resolution is given in the supplied text.

Sources & referencesView supporting material

Primary source

Michael D. Barrus and John Sinkovic, “Classes of critical graphs for tree-depth”, arXiv:1502.05277 (2015).

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.