The maximum-degree conjecture for critical graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.