Caro and Yuster's maximum-degree repetition conjecture
Statement
For an integer at least and a graph , let denote the order of . Define as the minimum cardinality of a set of vertices of such that has either vertices of maximum degree or order less than .
Caro and Yuster's conjecture. For every integer at least , there is a constant such that
for every graph .
The conjecture has the best possible growth rate in general: Caro and Yuster constructed graphs with . They verified it for and proved it for -free graphs, while the general assertion 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.