Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs

Jonatas Teodomiro; Xiao-Chuan Liu; Xu Yang

REVIEW 1 major objections 6 minor 13 references

Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs

T0 review · 1 major / 6 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that every red–blue coloring of the complete graph on $n$ vertices has a vertex cover by at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of one color, and that this bound is attained for infinitely many $n$.

desk verdict The upper bound ⌈√n⌉ is proved by a serious, checkable argument, and the result is new; but the printed sharpness example is garbled and must be repaired before the paper is publishable. read the letter →

arxiv 2608.27331 v1 pith:77LHUQRB submitted 2026-08-27 math.CO

Xiao-Chuan Liu , Jonatas Teodomiro , Xu Yang This is my paper · ORCID

classification math.CO MSC 05C1505C3805C7005C55

keywords monochromaticcyclecoversame-colorcyclestwo-edge-coloredcompletegraphcoveringnumberminimumcounterexamplebipartitecyclabilitydegree-sumcondition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves an exact bound for covering the vertices of a two-colored complete graph by monochromatic cycles of a single color. For every positive integer $n$, every red–blue edge-coloring of $K_n$ admits a cover by at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of the same color, where single vertices and edges count as degenerate cycles and cycles may overlap. The order of this bound is best possible, and the ceiling is necessary for infinitely many $n$, so the result is sharp, not just asymptotic. The proof extends the same-color path-cover conjecture to the cycle setting, where the cycle version can require one more component than the path version.

What carries the argument

The load-bearing object is the successor structure on a longest blue cycle $C=v_1\cdots v_\ell v_1$: for an outside vertex $z$, if $U_z$ is its set of blue neighbors on $C$, then the set $S_z$ of successors of $U_z$ on $C$ is a red clique, $z$ is red-complete to $S_z$, and $|S_z|<r$ where $r=n-(k-1)^2$. This converts blue-neighbor information into red cycles and enforces strong restrictions on how red and blue cycles can intersect. The other engine is a degree-sum cyclability theorem for bipartite graphs: for a 2-connected bipartite graph $H[A,B]$ with $|A|\ge|B|$, if $\sigma(T)\ge|A|+1$ for the minimum degree sum over nonedges touching $T$, then either a cycle covers $T$ or a specific exceptional alternative holds. The packing lemmas close cycles through the bipartite pieces and produce $Y$-spanning red cycles or contradictions.

What would settle it

The most direct falsifier is a single red–blue coloring of some $K_n$ with $n\ge6$ whose longest monochromatic cycle is shorter than $\lceil 2n/3\rceil$; this would invalidate inequality (3) and the packing argument that depends on it. Equally decisive would be a coloring of $K_{25}$ with no cover by five same-color cycles.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 1.2: for every positive integer $n$, every red–blue edge-coloring of $K_n$ has a cover by at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of one color. The proof runs by minimum counterexample. A longest monochromatic cycle, say blue, is fixed; its complement $Y$ is shown to have size at most $r-1$, where $r=n-(k-1)^2$ and $k=\lceil\sqrt{n}\rceil$. The successor structure on the blue cycle converts blue-neighbor information into red cliques, and bipartite degree-sum lemmas are used either to build a red cycle spanning $Y$ and part of $X$, or to force a contradiction with an intersection bound between red and blue cycles. Propositions eliminating all cases with $k\ge5$, together with finite case analyses for $k=4$ and $k=3$, complete the proof.

Load-bearing premise

The load-bearing premise is the known theorem that every red–blue $K_n$ with $n\ge6$ has a monochromatic cycle of length at least $\lceil 2n/3\rceil$; if that theorem failed or were weaker, the minimum-counterexample inequalities would not close.

Editorial extensions

If this is right

For every $n$, the exact worst-case number of same-color monochromatic cycles needed to cover any red–blue $K_n$ is $\lceil\sqrt{n}\rceil$.
When $\sqrt{n}$ is not an integer, the cycle version can require one more component than the same-color path version, and this gap is forced for infinitely many $n$.
No universal improvement below $\lceil\sqrt{n}\rceil$ is possible, because the bound is attained for infinitely many $n$.
The result upgrades the previously known order-of-magnitude estimate $\Theta(\sqrt{n})$ to the exact ceiling, with a proof that is uniform for all sufficiently large $n$ and finite for the remaining cases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same successor-clique mechanism could plausibly be adapted to $r$-color complete graphs, where the expected worst-case number of same-color cycles might grow like $r\sqrt{n}$; the paper does not address that setting.
The sharpness examples are essentially a large blue clique joined to a smaller independent set by red edges; testing random red–blue colorings and structured colorings at $n=k^2$ for small $k$ against the $\lceil\sqrt{n}\rceil$ bound would provide cheap computational evidence for tightness.
Because the proof allows degenerate cycles and intersecting covering pieces, the theorem may transfer directly to covering by monochromatic connected subgraphs with bounded treewidth, though that extension is not explored in the paper.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central discovery is Theorem 1.2: for every positive integer $n$, every red–blue edge-coloring of $K_n$ has a cover by at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of one color. The proof runs by minimum counterexample. A longest monochromatic cycle, say blue, is fixed; its complement $Y$ is shown to have size at most $r-1$, where $r=n-(k-1)^2$ and $k=\lceil\sqrt{n}\rceil$. The suc

/-- @claim 1 The central discovery is Theorem 1.2: for every positive integer $n$, every red–blue edge-coloring of $K_n$ has a cover by at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of one color. The proof runs by minimum counterexample. A longest monochromatic cycle, say blue, is fixed; its complement $Y$ is shown to have size at most $r-1$, where $r=n-(k-1)^2$ and $k=\lceil\sqrt{n}\rceil$. The suc -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main theorem is real: every red–blue K_n has a same-color cover by at most ⌈√n⌉ cycles. Prior work of Eugster–Mousset only gave Θ(√n), so the exact constant is new. The proof is a minimum-counterexample argument with a successor-clique structure, and I went through the core lemmas (2.1–2.7, 3.1–3.7, Propositions 4.1–4.3). The machinery is coherent. The use of the Faudree–Lesniak–Schiermeyer long-cycle theorem is standard and the inequality (3) is correct. The appendix cases for k=4 and k=3 follow the same pattern and I did not find a gap. This is a substantial piece of work.

The soft spot is exactly where the reader and the stress test put it: the lower-bound construction in Section 1 is mangled. The text says “let n be such that √n+1 is an integer”, then sets |B|=⌊√n⌋. Taken literally that forces n to be a perfect square, and then the displayed identity √n+1=⌈√n⌉ is false. The intended construction is plainly n=k^2−1, |B|=k−1, |A|=k(k−1), with A a blue clique and everything else red. With that repair, blue needs k cycles and red needs at least |A|/(k−1)=k cycles, giving sharpness. As printed, the sharpness half of the central claim is unsupported and internally inconsistent. That is a load-bearing flaw for the claim “the ceiling is necessary”, but it is a typographical/repair problem, not a mathematical one. The upper bound does not depend on it.

Minor comments: the paper cites its predecessors properly (Pokrovskiy–Versteegen–Williams, Chen–Chen, Eugster–Mousset) and the overlap with [13] and [3] is acknowledged in the text. No circularity. The statement that “a single vertex and a single edge are degenerate cycles” is standard but worth flagging to readers, since “cycle” elsewhere means length at least 3; the convention is fine.

Who is this for? Extremal graph theorists working on Ramsey-type covering problems. It deserves a serious referee. The referee should focus on the appendix cases and on verifying the repair of the construction. I would send it out, with the expectation of a minor revision.

Recommendation: accept for refereeing; require the author to fix the sharpness example and the typo “√n+1=⌈√n⌉” before publication.

Referee Report

1 major / 6 minor

Summary. The paper proves Theorem 1.2: for every positive integer n, every red-blue edge-coloring of K_n admits a vertex cover by at most ceil(sqrt(n)) monochromatic cycles, all of the same color, and claims that this bound is best possible for infinitely many n. The proof proceeds by minimum counterexample, choosing a longest monochromatic cycle and analyzing the structure of the outside set through successor cliques, bipartite cyclability theorems (Okamura-Yamashita, Faudree-Lesniak-Schiermeyer), and exact packing lemmas. A uniform argument handles the range k = ceil(sqrt(n)) >= 5, with appendices treating k = 4 and k = 3. The introduction contains a construction intended to show sharpness.

Significance. If correct, the paper determines the exact universal constant for same-color monochromatic cycle covers in two-colored complete graphs, upgrading the previously known asymptotic Theta(sqrt(n)) estimate of Eugster and Mousset to the sharp bound ceil(sqrt(n)). The result is a natural cycle analogue of the Erdos-Gyarfas same-color path-cover conjecture and shows a genuine gap of one between the path and cycle versions. The proof machinery is a substantial contribution: the successor structure forms red cliques, the bipartite cyclability lemmas are adapted cleanly, and the packing arguments are carefully checked. The upper-bound proof appears sound and does not assume the target result. The main defect is the garbled sharpness construction in Section 1, which is internally inconsistent as printed; the repair is local and the sharpness claim is valid after replacing the construction with n = k^2 - 1.

major comments (1)

[Section 1, lower-bound construction] The sharpness example as printed is internally inconsistent and cannot support the claim that the bound is best possible. The text says 'Let n be such that sqrt(n)+1 is an integer' and then sets |B| = floor(sqrt(n)); for such n, sqrt(n) is an integer, so ceil(sqrt(n)) = floor(sqrt(n)), and the displayed identity floor(sqrt(n)) + 1 = ceil(sqrt(n)) is false. Worse, the blue cover described then requires floor(sqrt(n)) + 1 cycles, which exceeds the bound claimed in Theorem 1.2, so the example contradicts the theorem rather than proving sharpness. The intended construction is evidently n = k^2 - 1 with |B| = k - 1 and |A| = k(k - 1), all edges inside A blue and all remaining edges red. With this repair, blue needs |B| + 1 = k cycles, every red cycle contains at most k - 1 vertices of A, and covering A requires at least k red cycles, matching ceil(sqrt(n)) = k. The arithmetic in the displayed red-cycle calculation is also garbled as printed and should be rewritten as ceil(k(k-1)/(k-1)) = k. Since this is the only place where sharpness of the main bound is established, the correction is load-bearing for the central claim.

minor comments (6)

[Theorem 1.2 statement] In the displayed theorem, the bound is rendered as 'cover by at most [sqrt(n)]' with the ceiling symbol missing; it should read \lceil\sqrt{n}\rceil.
[Section 3, inequality (3)] The sentence introducing (3) conflates two separate facts: the minimality argument gives w >= k, while the Faudree-Lesniak-Schiermeyer theorem gives w <= floor(n/3). The derivation is correct, but splitting the sentence would improve clarity.
[Lemmas 3.4-3.7] The compressed notation 'y S_z B y' and 'Hamilton path through the red clique S, with its other end joined to y' is terse; a sentence specifying that the path endpoints are selected so that the displayed red attachment edges exist would help the reader verify the cycles.
[Appendix A] The displayed cycles such as 'yS u x_1 z_2 x_2 v x_3 z_3 x_4 y' rely on the one-sentence convention after Proposition A.1; it would be helpful to state explicitly that all vertices in a displayed cycle are distinct unless otherwise indicated, since the reader must otherwise check for accidental repeats.
[Section 1, construction paragraph] The phrase 'all remaining edges red' should explicitly state that edges inside B are also red; this is implicit in 'remaining' but deserves emphasis because the blue graph then consists of the clique A plus isolated vertices in B.
[Throughout] There are several LaTeX-level typesetting artifacts (garbled \lceil commands, malformed accents in the abstract) that should be cleaned in revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper-bound proof is a self-contained minimal-counterexample induction relying on external theorems; the printed sharpness example is internally garbled but that is a correctness defect, not circularity.

full rationale

The proof of Theorem 1.2 is a minimum-counterexample induction over n. The bound k = ceil(sqrt(n)) is used only through the inductive hypothesis: in Lemma 3.2, if a red cycle and a blue cycle meet in at least r vertices, then n - |S| <= (k-1)^2, so the smaller complete graph has a same-color cover with at most k-1 cycles by minimality, and adding the relevant cycle gives the contradiction. This is legitimate induction, not a circular reduction. The load-bearing external ingredients, the Faudree-Lesniak-Schiermeyer long-cycle theorem and the Okamura-Yamashita cyclability theorem, are stated as standard results independent of the present claim; their assumptions do not include the target bound. The successor-structure lemmas (Lemma 3.3 and onward) are proved directly from edge-color contradictions and the intersection bound, and Propositions 4.1-4.3 together with Appendices A and B eliminate all minimum counterexamples by explicit red/blue cycle constructions. The authors do not rely on their own prior work, and no fitted parameter is renamed as a prediction. The sharpness example in Section 1 is mathematically garbled as printed: the identity floor(sqrt(n)) + 1 = ceil(sqrt(n)) is false when sqrt(n) is an integer, and the numerical relations do not close for the stated choice of n. The evident repair is n = k^2 - 1 with |B| = k-1, which would establish sharpness. That is a correctness issue in the lower-bound construction, but it is not a circular derivation. Overall, no step reduces by definition or self-citation to the result being proved.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on two external theorems (Okamura–Yamashita and Faudree–Lesniak–Schiermeyer) plus elementary graph theory. No free parameters or invented entities are introduced. The proof's novelty lies in the successor-structure and cycle-closing arguments, not in new axioms.

assumptions (3)

standard math Okamura–Yamashita cyclability theorem (Theorem 2.1)
Used as a black box to prove all bipartite cycle lemmas (Lemmas 2.2–2.5) and the red Y-spanning cycle lemmas.
standard math Faudree–Lesniak–Schiermeyer long-cycle theorem (long monochromatic cycle of length at least ⌈2n/3⌉)
Invoked in Section 3 to ensure the longest monochromatic cycle has length |X|≥⌈2n/3⌉, leading to w≤⌊n/3⌋.
standard math Elementary fact: a graph with matching number at most one is a star or triangle plus isolated vertices
Used in Appendix A to analyze the blue graph on Y when a1=3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs." pith.science (2026). https://pith.science/paper/77LHUQRB

@misc{pith2026260827331,
  author       = {Pith},
  title        = {Pith review of: Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/77LHUQRB}},
  note         = {Machine review of arXiv:2608.27331}
}

abstract

We extend the conjecture of Erd\H{o}s and Gy\'arf\'as on monochromatic path covers to the setting of monochromatic cycle covers. We prove that, for all $n$, every 2-edge-coloring of the complete graph on $n$ vertices contains a collection of at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of the same color, that together cover all vertices. The order of the bound is best possible, and the ceiling is necessary for infinitely many $n$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[13]

Pokrovskiy, L

A. Pokrovskiy, L. Versteegen, and E. Williams. A proof of a conjecture of Erd ˝os and Gy ´arf´as on monochromatic path covers.Journal of Combinatorial Theory, Series B, 176:551–560, 2026. 16 XIAO-CHUAN LIU, JONATAS TEODOMIRO, AND XU YANG (Liu) DEPARTAMENTO DEMATEM ´ATICA, UNIVERSIDADEFEDERAL DEPERNAMBUCO, AVENIDA JORNALISTAAN ´IBALFERNANDES, CIDADEUNIVERS...

work page 2026
[3]

On monochromatic path covers conjecture of Erd\H{o}s--Gy\'arf\'as

H. Chen and Y. Chen. On monochromatic path covers conjecture of Erd ˝os–Gy´arf´as.arXiv preprint arXiv:2607.21915, 2026

work page Pith review arXiv 2026
[1]

P . Allen. Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles. Combinatorics, Probability and Computing, 17(4):471–486, 2008

work page 2008
[2]

Bessy and S

S. Bessy and S. Thomass ´e. Partitioning a graph into a cycle and an anticycle, a proof of Lehel’s conjecture.Journal of Combinatorial Theory, Series B, 100(2):176–180, 2010

work page 2010
[4]

Erd˝os and A

P . Erd˝os and A. Gy ´arf´as. Vertex covering with monochromatic paths.Mathematica Pannonica, 6:7– 10, 1995

work page 1995
[5]

Erd˝os, A

P . Erd˝os, A. Gy´arf´as, and L. Pyber. Vertex coverings by monochromatic cycles and trees.Journal of Combinatorial Theory, Series B, 51:90–95, 1991

work page 1991
[6]

Eugster and F

M. Eugster and F. Mousset. Vertex covering with monochromatic pieces of few colours.Electronic Journal of Combinatorics, 25(3):P3.33, 2018

work page 2018
[7]

R. J. Faudree, L. Lesniak, and I. Schiermeyer. On the circumference of a graph and its complement. Discrete Mathematics, 309(19):5891–5893, 2009

work page 2009

Show all 13 references

[8]

Gerencs ´er and A

L. Gerencs ´er and A. Gy ´arf´as. On Ramsey-type problems.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math, 10:167–170, 1967

1967
[9]

Gy ´arf´as

A. Gy ´arf´as. Vertex coverings by monochromatic paths and cycles.Journal of Graph Theory, 7:131– 135, 1983

1983
[10]

Gy ´arf´as

A. Gy ´arf´as. Vertex covers by monochromatic pieces—a survey of results and problems.Discrete Mathematics, 339(7):1970–1977, 2016

1970
[11]

Łuczak, V

T. Łuczak, V . R ¨odl, and E. Szemer ´edi. Partitioning two-coloured complete graphs into two monochromatic cycles.Combinatorics, Probability and Computing, 7(4):423–436, 1998

1998
[12]

Okamura and T

H. Okamura and T. Yamashita. Degree sum conditions for cyclability in bipartite graphs.Graphs and Combinatorics, 29(4):1077–1085, 2013

2013

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.

[1] [13]

Pokrovskiy, L

A. Pokrovskiy, L. Versteegen, and E. Williams. A proof of a conjecture of Erd ˝os and Gy ´arf´as on monochromatic path covers.Journal of Combinatorial Theory, Series B, 176:551–560, 2026. 16 XIAO-CHUAN LIU, JONATAS TEODOMIRO, AND XU YANG (Liu) DEPARTAMENTO DEMATEM ´ATICA, UNIVERSIDADEFEDERAL DEPERNAMBUCO, AVENIDA JORNALISTAAN ´IBALFERNANDES, CIDADEUNIVERS...

work page 2026

[2] [3]

On monochromatic path covers conjecture of Erd\H{o}s--Gy\'arf\'as

H. Chen and Y. Chen. On monochromatic path covers conjecture of Erd ˝os–Gy´arf´as.arXiv preprint arXiv:2607.21915, 2026

work page Pith review arXiv 2026

[3] [1]

P . Allen. Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles. Combinatorics, Probability and Computing, 17(4):471–486, 2008

work page 2008

[4] [2]

Bessy and S

S. Bessy and S. Thomass ´e. Partitioning a graph into a cycle and an anticycle, a proof of Lehel’s conjecture.Journal of Combinatorial Theory, Series B, 100(2):176–180, 2010

work page 2010

[5] [4]

Erd˝os and A

P . Erd˝os and A. Gy ´arf´as. Vertex covering with monochromatic paths.Mathematica Pannonica, 6:7– 10, 1995

work page 1995

[6] [5]

Erd˝os, A

P . Erd˝os, A. Gy´arf´as, and L. Pyber. Vertex coverings by monochromatic cycles and trees.Journal of Combinatorial Theory, Series B, 51:90–95, 1991

work page 1991

[7] [6]

Eugster and F

M. Eugster and F. Mousset. Vertex covering with monochromatic pieces of few colours.Electronic Journal of Combinatorics, 25(3):P3.33, 2018

work page 2018

[8] [7]

R. J. Faudree, L. Lesniak, and I. Schiermeyer. On the circumference of a graph and its complement. Discrete Mathematics, 309(19):5891–5893, 2009

work page 2009