Problem 800

If $G$ is a graph on $n$ vertices which has no two adjacent vertices of degree $\geq 3$ then

R(G)\ll n,

where the implied constant is absolute.

Source: erdosproblems.com/800

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED and its curator credits Alon [Al94]; the proof is Alon's Proposition 1.3, which gives the absolute bound $R(G)\leq12n$ for this exact class. This is a published-source assessment, distinct from independent acceptance of a local proof reconstruction. The frontmatter standing is derived from the claim pages: Alon's theorem is an accepted full claim on the site curator's acceptance and its refereed publication (claim page (Alon, 1994)); the later $6n$ bound of Li, Rousseau and Šoltés, claims checked against the abstract only, is a second accepted full claim on its refereed publication (claim page (Li, Rousseau and Šoltés, 1997)).

BuEr75: S. A. Burr and P. Erdős, On the magnitude of generalized Ramsey numbers for graphs, in Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, Colloq. Math. Soc. János Bolyai 10, North-Holland, Amsterdam, 1975, 215--240, MR 371701. Theorem 6.1, printed p. 234, and the sentence after its proof, p. 236 (edition read: the Rényi archive copy, https://users.renyi.hu/~p_erdos/1975-26.pdf). Library home: Burr and Erdős 1975.
Al94: Noga Alon, Subdivided graphs have linear Ramsey numbers, Journal of Graph Theory 18(4) (1994), 343--347, DOI 10.1002/jgt.3190180406.
LRS97: Yusheng Li, Cecil C. Rousseau and Ľubomír Šoltés, Ramsey linear families and generalized subdivided graphs, Discrete Mathematics 170(1--3) (1997), 269--275, DOI 10.1016/S0012-365X(96)00311-1.

Problem 800

Status

Proof claims

Discussion