The maximum-degree conjecture for critical graphs

A graph is critical with tree-depth kk if its tree-depth is kk and every proper minor has smaller tree-depth. The maximum degree of a graph GG is denoted by δ(G)\delta(G).

The maximum-degree conjecture. Every critical graph with tree-depth kk has maximum degree at most

k1.k-1.

The bound is proved for the class of 11-unique critical graphs, and several classes of critical graphs are known to lie in that class. Whether every critical graph satisfies the bound remains open.

Sources & referencesView supporting material

Primary source

Michael D. Barrus and John Sinkovic, “Uniqueness and minimal obstructions for tree-depth”, arXiv:1310.1116 (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.