On the anti-Ramsey number of forests

Chunqiu Fang; Ervin Gy\H{o}ri; Jimeng Xiao; Mei Lu

REVIEW 3 major objections 5 minor 21 references

On the anti-Ramsey number of forests

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper determines exactly how many colors in a complete graph force a rainbow copy of any star forest, and pins down the approximate threshold for linear forests.

desk verdict The star-forest, 2P4, and double-star results are solid, but the linear-forest section contains a false lower-bound proposition (P2∪P3 gives 4 while Theorem 5(6) gives 2); the asymptotics likely survive a fix. read the letter →

arxiv 1908.04129 v1 pith:WMHQKBNG submitted 2019-08-12 math.CO

Chunqiu Fang , Ervin Győri , Mei Lu , Jimeng Xiao This is my paper · ORCID

classification math.CO MSC 05C5505C1505C35

keywords anti-Ramseynumberrainbowsubgraphstarforestlineardoubleedge-coloringrepresentingTurán

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

An edge-coloring of a complete graph is rainbow-free for a graph $G$ when no copy of $G$ has all its edges in distinct colors; the anti-Ramsey number $ar(K_n,G)$ is the largest number of colors that can be used without creating such a rainbow $G$. This paper proves an exact formula for $ar(K_n,F)$ when $F$ is a forest made of stars, valid for all large $n$, in terms of the star sizes and the number of stars. It also proves that for forests made of paths, the anti-Ramsey number is $(\sum_i \lfloor p_i/2 \rfloor - \epsilon)n + O(1)$, where $\epsilon$ depends only on whether all path lengths are odd, pinning the linear term exactly but leaving the constant unspecified. Two other exact results are included: $ar(K_n, 2P_4) = \max\{2n-2, 16\}$ for $n\ge 8$, and an exact formula for double stars $S_{p,q}$ for large $n$.

What carries the argument

The main device is the representing subgraph: a spanning subgraph of the colored complete graph that keeps exactly one edge of each color, so counting its edges counts the colors. The upper-bound arguments impose degree constraints on this subgraph: if some vertex is incident to many distinct colors, one can detach a star component and build a rainbow forest by induction; otherwise every vertex has bounded color-degree, and counting edges in the representing subgraph against the forbidden forest forces a rainbow copy. For star forests, the extremal colorings come from coloring a join $K_{i-1} + K_{n-i+1}$ rainbow and coloring the remaining clique with the star anti-Ramsey number. For linear forests, the proof uses a longest-rainbow-path method, partitioning the leftover vertices into three classes and bounding the edges in each via extremal estimates on paths and long cycles. For double stars, a degree lemma bounds the number of colors when every vertex sees at most a prescribed number of distinct colors, extending the star argument.

What would settle it

A computer search for a 17-coloring of $K_8$ with no rainbow $2P_4$ would directly test Theorem 10; finding one would disprove it. For the star-forest formula, checking a specific small case such as $F=K_{1,3}\cup K_{1,3}$ at the stated $n$ bound against the formula would expose any error in the induction. For the linear-forest theorem, writing out the omitted $s<6$ cases is the direct check; a counterexample to the claimed $(\sum_i \lfloor p_i/2\rfloor - \epsilon)n + O(1)$ form in one of those small cases would falsify the theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 8: for a star forest $F = \bigcup_{i=1}^t K_{1,p_i}$ with $p_1\ge 3$ and $p_1\ge \cdots \ge p_t\ge 1$, whenever $n\ge 3t^2(p_1+1)^2$, the anti-Ramsey number is the maximum of two kinds of terms: $(i-1)n - \binom{i}{2} + \lfloor (p_i-2)(n-i+1)/2 \rfloor + 1$ over those stars with at least two leaves, and $(t-2)n - \binom{t-1}{2} + r$, where $r=1$ if $p_{t-1}=1$ and $r=2$ otherwise. The paper further claims that a linear forest with path orders $p_1,\dots,p_k$ satisfies $ar(K_n,F) = (\sum_i \lfloor p_i/2 \rfloor - \epsilon)n + O(1)$, with $\epsilon=1$ when all $p_i$ are odd and $\epsilon=2$ otherwise. It also establishes the exact values for $2P_4$ and for double stars, and shows that a natural additive conjecture for disjoint tree copies fails for paths of length at least four.

Load-bearing premise

The proof of the linear-forest upper bound is written only for the case where the single even path has at least twelve vertices; the smaller cases are dismissed as provable by similar arguments without being written out, and the approximate linear-forest formula depends on those omitted cases.

Editorial extensions

If this is right

For any fixed star forest, the exact anti-Ramsey number is now known for all sufficiently large complete graphs, so the threshold color count can be read directly from the star sizes.
The linear-forest formula shows that the natural additive conjecture for disjoint tree copies fails for paths of length at least 4.
The exact value for $2P_4$ settles the smallest multi-path case not covered by earlier results, giving $2n-2$ once $n\ge 9$.
Double stars, the simplest non-star trees with two centers, have anti-Ramsey numbers matching the star threshold when one leaf class is smaller, and a slightly different threshold when the two centers have equal leaf counts.
The results provide exact data points connecting anti-Ramsey numbers to Tur\'an-type extremal numbers for disconnected forests.

Reading between the lines

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

Beyond the paper: the star-forest formula mirrors the Tur\'an number of the same forest but with $p_i-2$ in place of $p_i-1$, suggesting a general template in which the rainbow threshold is the extremal edge bound with the per-component parameter lowered by one and one color added.
Beyond the paper: completing the omitted small cases $s<6$ in the linear-forest proof would convert the $O(1)$ into an exact formula, and those omitted cases appear to be the only obstacle to a fully explicit constant.
Beyond the paper: the same representing-subgraph and degree-lemma arguments could be tested on spiders with three legs, where the paper's closing conjecture predicts a sharp lower bound; checking that conjecture on a concrete spider is a direct next step.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Colleague,

The paper is a mixed bag: the exact results for star forests (Thm 8), 2P4 (Thm 10), and double stars (Thm 11) are real contributions, and the proofs check out in the main counting steps. The authors adapt known techniques cleanly, and they credit Jiang, Simonovits–Sós, Gilboa–Roditty, and Lidický–Liu–Palmer properly. If I worked in anti-Ramsey theory, I would want these theorems in the literature.

The soft spot is Section 3. Proposition 1, the lower bound for linear forests, is false as stated. For F = P2∪P3 (p1=2, p2=3), the first term gives (5−2 choose 2)+1 = 4, while the paper's own Theorem 5(6) says ar(Kn, P2∪P3) = 2. The construction fails: color a K3 rainbow and all other edges with one extra color; that coloring contains a rainbow P2∪P3 (two adjacent rainbow edges plus a disjoint extra-colored edge). The same issue arises for 2P2. So the statement needs repair, and the proof of the first lower bound is invalid as written.

What does this do to the main results? Corollary 1 and the lower bound of Theorem 12 both invoke Proposition 1. However, the lower bound actually needed for the linear forest asymptotics is the second term of Proposition 1, coming from the join construction, and that construction appears sound. So I expect Theorem 9 to survive if the authors drop or fix the first term and re-route the proof through the second construction. But it is not something a referee should have to reverse-engineer.

There is also the acknowledged gap in Theorem 12: the proof only handles s ≥ 6 and punts on s < 6 with "similar arguments." Since Theorem 9 depends on Theorem 12, that needs to be filled in the revision. It may be routine, but it is load-bearing.

The rest of the paper looks solid. The 2P4 proof is a case analysis but coherent; the double-star argument via the representing subgraph and the lemma on degree-color constraints is neat.

Bottom line: worth sending to a serious referee. The revision should fix Proposition 1 and complete the small-s cases. I would accept it for peer review.

Referee Report

3 major / 5 minor

Summary. The paper studies anti-Ramsey numbers ar(K_n,F) for forests F. It claims an exact formula for star forests (Theorem 8), an approximate formula for linear forests (Theorem 9), an exact value for 2P4 (Theorem 10), and an exact formula for double stars (Theorem 11). The proofs use prior results of Jiang, Simonovits-Sós, Gilboa-Roditty, and Lidický-Liu-Palmer, together with counting arguments on representing subgraphs, rainbow paths, and degree-constrained colorings.

Significance. If correct, the star-forest theorem would be a genuine extension of known matching and star results, and the double-star theorem would provide new exact values for a natural family of trees. The paper also gives a plausible route to the asymptotic anti-Ramsey number of all linear forests. Strengths include explicit lower-bound colorings and a detailed induction for star forests. However, the linear-forest section contains a false lower-bound proposition and an explicitly omitted small case, and Section 4 relies on an unjustified reduction to triangles, so the paper is not yet in publishable form.

major comments (3)

[Section 3, Proposition 1] The first lower-bound construction is invalid. For F=P2∪P3, the construction colors a K_{Σp_i−2}=K3 rainbow and gives one new color to all remaining edges. This coloring contains a rainbow P2∪P3: choose a P3 on two edges of the rainbow K3 and, since n≥5, the disjoint edge between the two vertices outside the K3. Hence the claimed lower bound of 4 is not established, and it contradicts Theorem 5(6), which gives ar(K_n,P2∪P3)=2 for large n. Because Corollary 1 and Theorem 12 use Proposition 1 for their lower bounds, the lower-bound side of the linear-forest results is unsound as written. The asymptotic coefficient in Theorem 9 may be recoverable by deleting or correcting the first term, but the proposition as stated is false.
[Section 3, Theorem 12] The proof is carried out only for s≥6; the text says the case s<6 'can be proved by the similar arguments but need to distinguish more cases as in [20]' without giving any details. Since Theorem 12 is stated for all s≥1 and Theorem 9 depends on it, the missing verification of s=1,…,5 is load-bearing. The authors should either supply a complete proof for those cases or explicitly restrict the theorem and explain how Theorem 9 is obtained.
[Section 4, Lemma 1 and Theorem 10] After applying Theorem 3, the proof states 'Then k=3' without justification. A graph in Ω2 can consist of two disjoint cycles of length at least 4 (for example C4∪C4), which contains no triangle plus a disjoint cycle; hence the reduction to a rainbow C3∪C_l is not immediate from Theorem 3. The subsequent case analysis depends entirely on this reduction. Please provide a proof of the reduction or a precise citation of a strengthening of Theorem 3 that guarantees a rainbow triangle together with a vertex-disjoint cycle.

minor comments (5)

[Section 2, Theorem 8] In the statement, p_{t−1} is undefined when t=1; the formula for the second term should be restricted to t≥2, since the proof already treats t=1 separately.
[Sections 2 and 3, lower-bound constructions] The notation K_s + K_{n-s} (and similarly K_{i-1}+K_{n-i+1}) is ambiguous: it suggests the join of two complete graphs, but the subsequent instruction to color the edges of K_{n-s} with only a few colors indicates a different intended coloring. Please clarify the notation.
[Section 4, Lemma 1, Case 2] The displayed cycle C_3^4 = zx1x3x1z contains a repeated vertex; it should presumably be zx1x3z.
[Theorem 5, quoted formulas] The displayed formulas in Theorem 5 contain apparent typographical errors, such as 't/2' where a binomial coefficient is likely intended; please proofread the quoted statements against the original sources.
[Section 4, Fact 1] Fact 1 is described as trivial but is not immediate to me: a rainbow K6 on six vertices alone cannot host two vertex-disjoint P4s, so the fact relies on the colors of edges incident to the remaining vertices. A short justification would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proofs rely on external theorems and independent constructions, with no fitting or self-citation chain.

full rationale

The paper's derivation chain is not circular. The anti-Ramsey bounds are obtained from explicit lower-bound colorings (e.g., rainbow joins plus one color, rainbow K_{sum p_i - 2} plus one color, matchings via Theorem 4 and Theorem 5(6)) and upper-bound arguments by induction and by reduction to known external results of Jiang, Simonovits-Sos, Gilboa-Roditty, Lidicky-Liu-Palmer, Erdos-Gallai, Schiermeyer, and Jin-Li. No parameter is fitted to a subset of data and then renamed a prediction; no cited uniqueness theorem is imported from the authors' own prior work; and no ansatz is smuggled in through self-citation. The reference list contains no paper by the present authors, so the self-citation concern does not arise. Two passages deserve note but are not circularity: Proposition 1's first lower-bound construction appears to be false as stated (for P2 ∪ P3 it claims 4 colors while Theorem 5(6) gives 2, and the rainbow K3 plus one extra color does contain a rainbow P2 ∪ P3), and Theorem 12 omits the case s < 6 by saying it can be proved by similar arguments as in [20]. These are correctness and completeness defects, not instances of assuming what is proved. In particular, the later theorems do not reduce to Proposition 1's false claim by construction; they cite it as a lower bound, but that is an ordinary dependency, not circularity. Since every load-bearing theorem is either proved from independent external results or by direct case analysis, the appropriate circularity score is 0.

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

The paper is a pure combinatorics proof; it introduces no free parameters or new entities. It relies on a body of prior theorems (stars, paths, matchings, Turán numbers) which are cited and used without proof. These are treated as axioms in the ledger.

assumptions (6)

domain assumption Jiang (2002) and Montellano-Ballesteros (2006) anti-Ramsey number of stars
Used in Theorems 8 and 11 to handle single-star cases and to supply lower bounds.
domain assumption Gilboa-Roditty (2016) anti-Ramsey numbers for graphs with small components (Theorem 5)
Used for lower bounds in Theorem 8 involving tK2 and (t−1)K1,2 ∪ K2, and for known P3 cases.
domain assumption Simonovits-Sós (1984) exact anti-Ramsey number for paths
Used in Corollary 1 for all-even linear forests.
domain assumption Jin-Li (2009) anti-Ramsey number for two independent cycles
Used in Theorem 10 to obtain a starting rainbow union of two cycles.
domain assumption Lidický-Liu-Palmer (2013) Turán numbers of linear forests
Used in Corollary 1 to bound ar by ex for all-odd linear forests.
standard math Erdős-Gallai extremal bounds for paths and cycles
Used in Claims 1 and 3 of Theorem 12.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the anti-Ramsey number of forests." pith.science (2026). https://pith.science/paper/WMHQKBNG

@misc{pith2026190804129,
  author       = {Pith},
  title        = {Pith review of: On the anti-Ramsey number of forests},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WMHQKBNG}},
  note         = {Machine review of arXiv:1908.04129}
}

abstract

We call a subgraph of an edge-colored graph rainbow subgraph, if all of its edges have different colors. The anti-Ramsey number of a graph $G$ in a complete graph $K_{n}$, denoted by $ar(K_{n}, G)$, is the maximum number of colors in an edge-coloring of $K_{n}$ with no rainbow subgraph copy of $G$. In this paper, we determine the exact value of the anti-Ramsey number for star forests and the approximate value of the anti-Ramsey number for linear forests. Furthermore, we compute the exact value of $ar(K_{n}, 2P_{4})$ for $n\ge 8$ and $ar(K_{n}, S_{p,q})$ for large $n$, where $S_{p,q}$ is the double star with $p+q$ leaves.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages

[20]

Simonovits and V.T

M. Simonovits and V.T. S´ os, On restricted colorings of Kn, Combinatorica 4(1): 101-110, 1984

work page 1984
[1]

Alon, On a conjecture of Erd˝ os, Simonovits and S´ os co ncerning anti-Ramsey theorems, J

N. Alon, On a conjecture of Erd˝ os, Simonovits and S´ os co ncerning anti-Ramsey theorems, J. Graph Theory 7(1): 91-94, 1983

work page 1983
[2]

Bialostocki, S

A. Bialostocki, S. Gilboa and Y. Roditty, Anti-Ramsey nu mbers of small graphs, Ars. Combinatoria 123: 41-53, 2015. 16

work page 2015
[3]

Bushaw and N

N. Bushaw and N. Kettle, Tur´ an numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20: 837-853, 2011

work page 2011
[4]

H. Chen, X. Li and J. Tu, Complete solution for the rainbow number of matchings, Discrete math. 309(10): 3370-3380, 2009

work page 2009
[5]

Erd˝ os and T

P. Erd˝ os and T. Gallai, On maximal paths and circuits of g raphs, Acta math. Acad. Sci. Hung. 10: 337-356, 1959

work page 1959
[6]

Erd˝ os, M

P. Erd˝ os, M. Simonovits and V. T. S´ os, Anti-Ramsey theorems, In Inﬁnite and ﬁnite sets, Vol. II, pages 633-643. Colloq. Math. Soc. J´ anos Bolyai, Vol. 10. North-Holland, Amsterdam, 1975

work page 1975
[7]

Fujita, C

S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizati ons of Ramsey theory: A survey, Graphs Combin. 26: 1-30, 2010

work page 2010

Show all 21 references

[8]

Fujita, C

S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizati ons of Ramsey theory - A Dynamic Survey, https://digitalcommons.georgiasouthern.edu/tag
[9]

Gilboa and Y

S. Gilboa and Y. Roditty, Anti-Ramsey numbers of graphs w ith small connected compo- nents, Graphs Combin. 32: 649-662, 2016

2016
[10]

Gorgol and A

I. Gorgol and A. G¨ orlich, Anti-Ramsey numbers for disj oint copies of graphs, Opuscula Math. 37(4): 567-575, 2017

2017
[11]

Haas and M

R. Haas and M. Young, The anti-Ramsey number of perfect m atching, Discrete Math. 312(5): 993-937, 2012

2012
[12]

Jiang, Edge-coloring with no large polychromatic st ars, Graphs Combin

T. Jiang, Edge-coloring with no large polychromatic st ars, Graphs Combin. 18(2): 303-308, 2002

2002
[13]

Jiang and D

T. Jiang and D. B. West, Edge colorings of complete graph s that avoid polychromatic trees, Discrete Math. 274: 137-147, 2004

2004
[14]

Jin and X

Z. Jin and X. Li, Anti-ramsey numbers for graphs with ind ependent cycles, Electron. J. Combin., 16: Research Paper 85, 2009

2009
[15]

Lidick´ y, H

B. Lidick´ y, H. Liu and C. Palmer, On the Tur´ an number of forests, Electron. J. Combin. 20(2), 2013

2013
[16]

Montellano-Ballesteros and V

J.J. Montellano-Ballesteros and V. Neumann-Lara, An a nti-Ramsey theorem, Combinator- ica 22(3): 445-449, 2002

2002
[17]

Montellano-Ballesteros and V

J.J. Montellano-Ballesteros and V. Neumann-Lara, An a nti-Ramsey theorem on cycles, Graphs Combin. 21(3): 343-354, 2005

2005
[18]

Montellano-Ballesteros, On totally multicolore d stars, J

J.J. Montellano-Ballesteros, On totally multicolore d stars, J. Graph Theory 51(3): 225-243, 2006. 17

2006
[19]

Schiermeyer, Rainbow numbers for matchings and comp lete graphs, Discrete Math

I. Schiermeyer, Rainbow numbers for matchings and comp lete graphs, Discrete Math. 286(1- 2): 157-162, 2004

2004
[21]

Yuan and X

L. Yuan and X. Zhang, Anti-Ramsey numbers of graphs with some decomposition family sequences, arXiv preprint arxiv: 1903.10319v1, 2019. 18

1903 arXiv

Pith tools

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

[1] [20]

Simonovits and V.T

M. Simonovits and V.T. S´ os, On restricted colorings of Kn, Combinatorica 4(1): 101-110, 1984

work page 1984

[2] [1]

Alon, On a conjecture of Erd˝ os, Simonovits and S´ os co ncerning anti-Ramsey theorems, J

N. Alon, On a conjecture of Erd˝ os, Simonovits and S´ os co ncerning anti-Ramsey theorems, J. Graph Theory 7(1): 91-94, 1983

work page 1983

[3] [2]

Bialostocki, S

A. Bialostocki, S. Gilboa and Y. Roditty, Anti-Ramsey nu mbers of small graphs, Ars. Combinatoria 123: 41-53, 2015. 16

work page 2015

[4] [3]

Bushaw and N

N. Bushaw and N. Kettle, Tur´ an numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20: 837-853, 2011

work page 2011

[5] [4]

H. Chen, X. Li and J. Tu, Complete solution for the rainbow number of matchings, Discrete math. 309(10): 3370-3380, 2009

work page 2009

[6] [5]

Erd˝ os and T

P. Erd˝ os and T. Gallai, On maximal paths and circuits of g raphs, Acta math. Acad. Sci. Hung. 10: 337-356, 1959

work page 1959

[7] [6]

Erd˝ os, M

P. Erd˝ os, M. Simonovits and V. T. S´ os, Anti-Ramsey theorems, In Inﬁnite and ﬁnite sets, Vol. II, pages 633-643. Colloq. Math. Soc. J´ anos Bolyai, Vol. 10. North-Holland, Amsterdam, 1975

work page 1975

[8] [7]

Fujita, C

S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizati ons of Ramsey theory: A survey, Graphs Combin. 26: 1-30, 2010

work page 2010