Does f(n)(log_2 n)^2/n converge, for f(n) the maximum chromatic-to-clique ratio on n vertices? (Erdős #627)
Statement
Let $\omega(G)$ denote the clique number of $G$ and $\chi(G)$ the chromatic number. If $f(n)$ is the maximum value of $\chi(G)/\omega(G)$, as $G$ ranges over all graphs on $n$ vertices, then does $$\lim_{n\to\infty}\frac{f(n)}{n/(\log_2 n)^2}$$ exist?
Acceptance. FULLY RESOLVES: a complete proof that the limit $\lim_n f(n)(\log_2 n)^2/n$ exists (ideally identifying its value), or a proof that it does not exist (limsup strictly greater than liminf). Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: a proof narrowing the interval containing the limsup and/or liminf strictly beyond the best bounds stated in the background; a proof of existence of the limit under strictly weaker hypotheses than the [AFM25] conditional result (e.g. removing or weakening the $R(s,t)\leq R(k)$ monotonicity assumption); or a proof determining the liminf or limsup exactly. All advances must be proofs — numerical experiments alone do not qualify. Deliver the proof file.
Background
Posed by Erdős across [Er61d], [Er67c], and [Er69b]; listed as open on erdosproblems.com/627 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). Tutte and Zykov [Zy52] independently showed the chromatic number can be arbitrarily large with clique number 2; Erdős [Er61d] gave $n$-vertex triangle-free graphs with $\chi \gg n^{1/2}/\log n$, hence $f(n)\gg n^{1/2}/\log n$. Erdős [Er67c] then pinned the order of growth, $f(n)\asymp n/(\log_2 n)^2$, and showed that the limit in question, if it exists, lies in $[1/4, 4]$ (he stated the upper constant as $1$, but Araujo, Filipe, and Miyazaki [AFM25] note his method actually yields $4$). [AFM25] tie the problem to Ramsey numbers: if $\lim_k \log R(k)/k$ exists and equals $C$ (that limit's existence is itself the famous Erdős #77, erdosproblems.com/77) and additionally $R(s,t)\leq R(k)$ whenever $st\leq k^2$, then the limit here exists and equals $C^2$; using this connection they improved the upper bound from $4$ to approximately $3.7$. The problem is also catalogued in the UCSD Erdős graph-problems collection. The attacker's tool: proof-shaped asymptotic extremal graph theory — sharpened Ramsey-type estimates or a direct argument controlling the extremal constant; exact computation of $f(n)$ for small $n$ (chromatic/clique search) can build intuition but cannot decide the limit.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #627 (T. F. Bloom) | website |
| REF-02 | UCSD Erdős graph problems: maximum of chi/omega | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.