Erdős Problem #87
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
The chromatic number \(\chi(G)\) is the minimum number of colours required to colour a graph's vertices without a monochromatic edge. Its Ramsey number \(R(G)\) is the least integer \(N\) such that every two-colouring of the edges of \(K_N\) contains a monochromatic copy of \(G\).
Erdős #87 asks whether, for every \(\epsilon>0\) and sufficiently large \(k\),
holds for every graph \(G\) with \(\chi(G)=k\), where \(R(k)=R(K_k)\). The stronger conjecture asks whether \(R(G)>cR(k)\) for a fixed positive \(c\) independent of \(k\). The order of these quantifiers is important.
A small example
For \(G=K_k\), equality \(R(G)=R(k)\) holds. It does not follow that every graph with chromatic number \(k\) has Ramsey number at least \(R(k)\). Faudree and McKay calculated the pentagonal wheel \(W\) has chromatic number four and \(R(W)=17\), whereas \(R(4)=18\). This refutes an older, stronger conjecture but not the revised large-parameter question.
For fixed \(k=4\), the proposed inequality can tolerate a discrepancy such as \(17/18\); an asymptotic claim is not decided by a single small value.
What is known
Both revised formulations are OPEN. The historical source is Erdős's 1995 problem list cited on Erdős #87, which also records the Faudree–McKay finite result and Wigderson's observation that a probabilistic red-blue colouring yields \(R(G)\gg2^{k/2}\) when \(\chi(G)=k\).
Because the standard diagonal bound gives \(R(k)\le4^k\), the displayed exponential comparison is automatic if \(\epsilon\ge3/4\). This does not address the interesting arbitrarily small positive \(\epsilon\) regime. The exact wheel computation and the original Erdős 1995 printed statement have not been independently page-checked here.
GCL's current state
The pinned catalogue and maintained page (January 2026) classify this problem OPEN. The original source assignment is #1356. This article distinguishes the failed strict inequality \(R(G)\ge R(k)\) from both open weakened versions, without promoting secondary bibliographic remarks to independent source-proof certification.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded verification task is to encode the small pentagonal-wheel example as a two-colour Ramsey SAT problem. Acceptance requires a two-colouring of \(K_{16}\) without a monochromatic wheel, a complete certificate that every two-colouring of \(K_{17}\) contains one, and a check that the wheel is four-chromatic. Stop at \(k=4\) and make no inference about large \(k\).
Sources and claim boundaries
- Erdős #87, original [Er95] and Faudree–McKay [FaMc93] references.
- GCL original issue #1356; pinned revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
No new Ramsey bound, independently verified 1993 computation, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1356 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.