Problem 627

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_2n)^2}

exist?

Source: erdosproblems.com/627

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label (page last edited 8 February 2026). The site's commentary records Erdős's bounds and the conditional theorem and improved constant of Araujo, Filipe and Miyazaki; the Current assessment records them with the conditional claim page Araujo, Filipe and Miyazaki's conditional limit.

AFM25: I. Araujo, R. Filipe, and R. Miyazaki, A note on the maximum ratio between chromatic number and clique number. arXiv:2512.16062 (2025).
Er61d: Erdős, P., Graph theory and probability. II. Canadian J. Math. (1961), 346-352.
Er67c: Erdős, P., Some remarks on chromatic graphs. Colloq. Math. (1967), 253-256.
Zy52: Zykov, A. A., On some properties of linear complexes. Amer. Math. Soc. Translation (1952), 33.

Problem 627

Status

Proof claims

Discussion