Problem 549

If $T$ is a tree which is a bipartite graph with $k$ vertices and $2k$ vertices in the other class then

R(T)=4k-1.

Source: erdosproblems.com/549

Graph theory
Ramsey theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved, the site's label (page last edited 28 December 2025), credited by the site's curator, T. F. Bloom, to Norin, Sun and Zhao. For $T=S(2k-1,k-1)$ , Norin, Sun and Zhao's Theorem 1.3 gives $R(T)\ge4.2k-o(k)$ , so $R(T)>4k-1$ for all large $k$ ; the paper says this answers the 1982 question in the negative. The status-defining source is an arXiv preprint (1605.03612v1, 2016); its lower bound is restated and relied on in refereed papers (Dubó and Stein, Discrete Math. 348 (2025)) and the site accepted it. Independently, the refereed Theorem 2.1 of [GHK79] (1979) gives $R(S(2k-1,k-1))\ge4k$ for every $k\ge4$ by an explicit coloring of $K_{4k-1}$ , so the equality fails at every $k\ge4$ (claim page (Grossman, Harary and Klawe, 1979)). The equality does hold for two families with classes $k$ and $2k$ (the brooms $B_{k,2k}$ and Burr and Erdős's trees made of a path on four vertices with stars on $2k-1$ and $k-1$ vertices at its ends) and, by Montgomery, Pavez-Signé and Yan (preprint, 2025), for every such tree of maximum degree at most $3ck$ for a small absolute $c>0$ ; each has a partial claim page (brooms, Burr and Erdős 1976, Montgomery, Pavez-Signé and Yan 2025). The claim page Norin, Sun and Zhao 2016 records the disproof, its posting and the acceptance evidence; the frontmatter standing is derived from the claim pages.

EFRS82: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Ramsey numbers for brooms. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congr. Numer. 35 (1982), 283--293. The lower bound, p. 285; Theorem 2.2, p. 286; the question, p. 292. Library home: Erdős 1982.
NSZ16: Norin, S., Sun, Y. R. and Zhao, Y., Asymptotics of Ramsey numbers of double stars. arXiv:1605.03612v1 (11 May 2016; the only version), 13 pp. Preprint. Theorem 1.3 and its consequence, p. 2; Theorem 4.5, p. 10; Questions 5.1--5.2, pp. 11--12. Library home: Norin and Zhao 2016.
DuSt24: Flores Dubó, F. and Stein, M., On the Ramsey number of the double star. arXiv:2401.01274 (v1 2 January 2024; v2 20 April 2024, the version cited); Discrete Math. 348 (2025), no. 1, 114227, doi:10.1016/j.disc.2024.114227. Theorem 2 and Corollary 3, p. 3 of v2. Library home: Dubó and Stein 2024.
MPY25: Montgomery, R., Pavez-Signé, M. and Yan, J., Ramsey numbers of trees. arXiv:2509.07934v1 (9 September 2025; the only version), 59 pp. Preprint; no journal record found. Theorem 1.1, p. 2. Library home: Montgomery, Pavez-Signé and Yan 2025.
BuEr76: Burr, S. A. and Erdős, P., Extremal Ramsey theory for graphs. Utilitas Math. 9 (1976), 247--258. Lemma 4.1 and Theorem 4.1, pp. 252--253. Library home: Burr and Erdős 1976.
Bu74: Burr, S. A., Generalized Ramsey theory for graphs---a survey. Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., 1973), Lecture Notes in Math. 406, Springer (1974), 52--75. Not held; the source of the two colorings and of the exact conjecture, quoted here from [NSZ16] p. 2 and [MPY25] p. 2.
GHK79: Grossman, J. W., Harary, F. and Klawe, M., Generalized Ramsey theory for graphs, X: double stars. Discrete Math. 28 (1979), no. 3, 247--254. Theorem 2.1 and Lemmas 2.2--2.4, pp. 248--249; Theorems 3.1--3.3, pp. 249--250; Lemma 3.9, p. 253; the conjecture and the remark on Burr's conjecture, p. 254. Library home: Grossman and Klawe 1979.

Problem 549

Status

Proof claims

Discussion