ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For an integer kk at least 22 and a graph GG, let n(G)n(G) denote the order of GG. Define fk(G)f_k(G) as the minimum cardinality of a set XX of vertices of GG such that G−XG-X has either kk vertices of maximum degree or order less than kk.

Caro and Yuster's conjecture. For every integer kk at least 22, there is a constant ckc_k such that

fk(G)≤ckn(G)f_k(G)\leq c_k \sqrt{n(G)}

for every graph GG.

The conjecture has the best possible growth rate in general: Caro and Yuster constructed graphs with f2(G)≥(1−o(1))n(G)f_2(G)\geq (1-o(1))\sqrt{n(G)}. They verified it for k∈{2,3}k\in\{2,3\} and proved it for C4C_4-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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.