Chen 2026 monochromatic path covers conjecture erdos gyarfas

../

theorem_1_5: The preprint's claim that for every positive integer n the vertex set of every two-colored complete graph on n vertices is covered by at most root n monochromatic paths of one color, the statement of Problem 518 for every n; a claim page, the argument unchecked here.

---

Hangdi Chen and Yaojun Chen, On monochromatic path covers conjecture of Erdős--Gyárfás. arXiv:2607.21915 [math.CO]; v1 posted 24 July 2026, the only version on 2026-09-18 (the arXiv record carried no journal reference or DOI; a Semantic Scholar citation request for the identifier answered HTTP 429 and was not repeated). An unrefereed preprint. On the site's Problem 518 proof-claims tab it is the one entry, "A full proof claimed by Hangdi Chen, Yaojun Chen", summary "This paper rules out counterexamples for all small remaining values of n, thereby proving that the result holds exactly for every n≥1", submitted 2026-07-29 by a site user with an external link to the proof and no comments; the site's label stayed PROVED with the resolution attributed to Pokrovskiy, Versteegen and Williams, and the problem page's commentary does not mention the preprint (refresh).

The copy read for this card is arXiv:2607.21915v1, 14 pages with a complete text layer, pp. 1--3, 13 and 14 read on the rendered page images and the rest in the text layer. Provenance: the arXiv PDF of version 1; 129,341 bytes. The arXiv record (https://arxiv.org/abs/2607.21915, read 2026-10-02) names the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 license.

Read status: claims checked for Theorems 1.1, 1.2, 1.4 and 1.5, Conjecture 1.3 and the conventions paragraph (pp. 1--2), each read clause by clause; the proof (Section 3, pp. 3--13, a minimal counterexample argument) was located and not read, and no step of the argument was checked. This card claims no correctness for the preprint's theorem; it records what the preprint states.

Contents

• Abstract and Section 1 (pp. 1--2): the conjecture ("Erdős and Gyárfás conjectured in 1995 that, in every red--blue edge-coloring of a complete graph $K_n$, the vertex set can be covered by at most $\sqrt n$ monochromatic paths, all of the same color", p. 1), Theorem 1.1 (Gerencsér and Gyárfás: two monochromatic paths cover the vertex set), Theorem 1.2 (Erdős and Gyárfás: at most $2\sqrt n$ paths of the same color), Conjecture 1.3 (the $\sqrt n$ form, attributed to Erdős and Gyárfás), Theorem 1.4 (Pokrovskiy, Versteegen and Williams, quoted with the threshold $n>20^{40}$) and Theorem 1.5 (p. 2), the claim: "For every positive integer $n$, the vertex set of every red--blue edge-colored $K_n$ can be covered by at most $\sqrt n$ monochromatic paths, all of the same color." Conventions (p. 2): paths may intersect, a single vertex is a path of either color, and a red path cover is a set of red paths covering every vertex.
• Section 2 (pp. 2--3): stated without proof, the cut-coloring lemma of Erdős and Gyárfás (Lemma 2.1), the monochromatic path on at least $\lfloor2n/3\rfloor+1$ vertices of Gerencsér and Gyárfás (Lemma 2.2) and three auxiliary lemmas of Pokrovskiy, Versteegen and Williams (Lemmas 2.3--2.5).
• Section 3 (pp. 3--13): the proof of Theorem 1.5 by a minimal counterexample, not read here.

Compiled scope

Pages 1--3 were read on the page images, with the close of Section 3 (p. 13) and the references (p. 14); the section headings, the statement labels of Section 3 and its citations of the Section 2 lemmas were read in the text layer. No proof was read and nothing here is independently reviewed.

Bears on. #518: Theorem 1.5 (p. 2) claims the site's statement for every $n\ge1$, closing the range $n\le20^{40}$ that the refereed theorem of Pokrovskiy, Versteegen and Williams leaves; recorded on that page as an unreviewed proof claim with its provenance, not as status.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.