Ramsey threshold for trees versus odd cycles

For an odd integer m≥3m\ge 3, determine the least integer f(m)f(m) such that, for every integer n≥f(m)n\ge f(m) and every tree TnT_n on nn vertices, the Ramsey number satisfies R(Tn,Cm)=2n−1R(T_n,C_m)=2n-1. The conjectured exact value is f(m)=⌈2m−13⌉f(m)=\left\lceil\frac{2m-1}{3}\right\rceil for every odd m≥5m\ge 5.

References

Primary source

arXiv

Additional references

Progress summary

Refreshed
Claimed progress

A new unrefereed preprint claims to determine the exact cutoff for tree-versus-odd-cycle colorings when the cycle is sufficiently long, but smaller cycle lengths remain unresolved.

Burr, Erdős, Faudree, Rousseau, and Schelp initiated the problem of finding the least threshold f(m)f(m) such that R(Tn,Cm)=2n−1R(T_n,C_m)=2n-1 for all sufficiently large nn, with mm odd. The central conjecture predicts f(m)=⌈(2m−1)/3⌉f(m)=\left\lceil(2m-1)/3\right\rceil for odd m≥5m\geq 5.

Known results

  • Burr, Erdős, Faudree, Rousseau, and Schelp (2016): f(m)≤756m10f(m)\leq 756m^{10}.
  • Brennan (2016): f(m)≤25mf(m)\leq 25m.
  • Fan and Lin (2025): f(m)≤4m−8f(m)\leq 4m-8.
  • Huang, Zhang, and Chen (2026): f(m)≤2m−4f(m)\leq 2m-4, with ⌈(2m−1)/3⌉≤f(m)\left\lceil(2m-1)/3\right\rceil\leq f(m); they stated the exact-threshold conjecture.

September 1, 2026 claimed resolution

A preprint identified on September 1, 2026 claims to settle the exact threshold for every sufficiently large odd mm and to confirm the Huang--Zhang--Chen conjecture in that range. This claim is unrefereed and has no independent verification in the retrieved material.

Current status (as of September 2026): The threshold is claimed to equal ⌈(2m−1)/3⌉\left\lceil(2m-1)/3\right\rceil for sufficiently large odd mm, but that claim is unverified and cases outside that range remain open.

Sources

Solutions 0

No solutions have been posted yet.