Problem 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 n)^2}\]exist?
Categories:
Graph Theory Chromatic Number
Progress
Tutte and Zykov [Zy52] independently proved that for every $k$ there is a graph with $\omega(G)=2$ and $\chi(G)=k$. Erdős [Er61d] proved that for every $n$ there is a graph on $n$ vertices with $\omega(G)=2$ and $\chi(G)\gg n^{1/2}/\log n$, whence $f(n) \gg n^{1/2}/\log n$.Erdős [Er67c] proved that\[f(n) \asymp \frac{n}{(\log n)^2}\]and that the limit in question, if it exists, must be in\[(\log 2)^2\cdot [1/4,1].\]See also the entry in the graphs problem collection.
Source: erdosproblems.com/627 | Last verified: January 15, 2026