The maximum-degree conjecture for critical graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.