The maximum-degree conjecture for critical graphs
A graph is critical with tree-depth if its tree-depth is and every proper minor has smaller tree-depth. The maximum degree of a graph is denoted by .
The maximum-degree conjecture. Every critical graph with tree-depth has maximum degree at most
The bound is proved for the class of -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.