The maximum-degree conjecture for critical graphs

About 13 years old · traced to

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

k−1.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.

References

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.