---

Statement

Problem 2 (printed p. 10). "Is Cor. 2 true with $\sqrt n$ instead of $2\sqrt n$?"

That is: can the vertex set of every 2-colored $K_n$ be covered by $\sqrt n$ monochromatic paths of the same color? The paper prints no construction here; the construction showing that $\sqrt n$ would be best possible is given by Pokrovskiy, Versteegen and Williams (2024), p. 1, who attribute the conjecture to Erdős and Gyárfás through Gyárfás's 2016 survey.

Source. P. Erdős and A. Gyárfás, Vertex covering with monochromatic paths, Math. Pannon. 6 (1995), no. 1, 7--10; Problem 2 on printed p. 10 (PDF p. 4 of the journal's own PDF, which has no usable text layer), read on the rendered page image. The problem is the last sentence of the paper before the references.

Read depth. Claims checked: the question was read clause by clause on the page image. A question, nothing to prove.

Bears on

• Problem 518: the problem's origin, in the words the site paraphrases; answered for all $n>20^{40}$ by Theorem 1.3 of Pokrovskiy, Versteegen and Williams.