---

Claim. Every graph $G$ with no $K_4$ minor, that is, every graph of treewidth at most $2$, is Ramsey size linear in the sense of Problem 566: for every graph $H$ with $m$ edges and no isolated vertices,

$$R(G,H)\le624\,v(G)\,m.$$

The claimant describes the method as an adaptation of two tools from the paper of Bradač, Gishboliner and Sudakov (the library's source card), triangle removal and an averaging step. Three further results are stated in the claimant's summary: a connected graph whose edge count exceeds its vertex count by at most two is Ramsey size linear unless $K_4$ or $K_4^*$ ($K_4$ with one edge subdivided, the $H_5$ of Problem 567) is a subgraph of it; one graph in each of the pairs $\{K_4^*,W_4\}$ and $\{W_5^-,W_5\}$ fails to be Ramsey size linear while all of its proper subgraphs are (the site's Problem 79); and an exhaustive computation over the graphs with at most eight vertices leaves, by the claimant's count, $49$ minimal graphs undecided under the density hypothesis, which fall into eleven core types, the code and tables being supplementary material of the preprint.

Submission note. Posted to erdosproblems.com as a proof claim by Gonzalo Barria (account gonzalobarria) on 29 September 2026, giving "Claude Opus 5.5" as the AI used:

I posted a preprint with partial progress on this problem: G. Barría, "Every K4-minor-free graph is Ramsey size-linear", Preprints (2026), https://doi.org/10.20944/preprints202609.2254.v1 Main result: every graph with no K4-minor (treewidth at most two) is Ramsey size-linear, with R(G,H) ≤ 624 v(G) e(H). This covers all 2-trees, which attain the density 2k−3 in the question. The proof combines the triangle-elimination and averaging arguments of Bradač, Gishboliner and Sudakov. Consequences: A connected graph with at most v(G)+2 edges is Ramsey size-linear unless it contains K4 or K4*. Each of the pairs {K4*, W4} and {W5−, W5} contains a minimally non-Ramsey size-linear graph (cf. #79). A computer search over all graphs on at most 8 vertices reduces the open cases of the question to 49 minimal graphs, governed by eleven cores. The code and full results are included as supplementary material. Notes: https://www.preprints.org/frontend/manuscript/1b1545e55d77c6ee2254cb513af51605/download_pub

Covers. The corrected Statement of Problem 566 (every subgraph on $k\ge2$ vertices has at most $2k-3$ edges) for the graphs without a $K_4$ minor. Every $2$-tree has exactly $2k-3$ edges and satisfies the hypothesis with equality, so the claim covers the extremal instances of that family; the density question for all graphs satisfying the hypothesis is not claimed.

Depends on. Nothing in this wiki; the argument adapts the methods of Bradač, Gishboliner and Sudakov rather than invoking a paged theorem.

Standing. Claimed. The claimant, Gonzalo Barría, posted the preprint "Every $K_4$-minor-free graph is Ramsey size-linear" on preprints.org (posted 28 September 2026, MDPI AG, Creative Commons Attribution 4.0, per its Crossref record) and submitted it on 29 September 2026, from the account gonzalobarria, to the site's claim tab, whose entry reads as a proof claimed by Gonzalo Barria using Claude Opus 5.5, with no partial marker; the claimant's summary presents it as partial progress and the manuscript's main result is the $K_4$-minor-free case, so the scope is recorded as partial on the claim's own statement. The claim had no comments on the tab as of 2026-10-07; the site's label is OPEN and its commentary does not mention the preprint (page last edited 18 January 2026); no arXiv version, journal record or independent review was found. Nothing in the manuscript is checked in this corpus, so no evidence kind is listed. A partial claim derives nothing for the problem's standing.