Ratio of chromatic number to clique number

A problem on the chromatic number and clique number (proposed by Erdös)

Let \(\omega(G)\) denote the number of vertices in a largest complete subgraph of \(G\). Let \(f(n)\) denote the maximum value of \(\chi(G)/\omega(G)\), where \(G\) ranges over all graphs on \(n\) vertices.
Does the following limit exist \[ \lim_{n \rightarrow \infty} \frac{f(n)}{ n/\log^2 n}? \]

Tutte and Zykov [1] independently showed that for every \( k\), there is a graph \( G\) with \(\omega(G)=2\) (i.e., \( G\) contains no triangle), and with \( \chi(G)=k\). Erdös [2] proved that for every \( n\), there is a graph \( G\) on \( n\) vertices with \(\omega(G)=2\) and \( \chi(G) > c n^{1/2}/\log n\). Using Kim's result [3] on Ramsey numbers, it follows there is a graph \( G\) on \( n\) vertices with \( \omega(G)=2\) and with chromatic number \( \chi(G)\) satisfying

\(\displaystyle (1+o(1)) \frac 1 9 \sqrt{\frac{n}{\log n}} <\chi(G). \)

For the maximum ratio \( f(n)\) of the chromatic number and the clique number, Erdös [4] proved that

\(\displaystyle \frac{c n}{\log^2 n} \leq f(n) \leq \frac{c'n}{\log^2 n}. \)

The value of the limit of \( f(n)/(n/\log^2 n)\), if it exists, is shown in [4] to be between \( (\log n)^2/4\) and \( (\log 2)^2\).

1 A. A. Zykov, On some problems of linear complexes, Mat. Sbornik N. S. 24 (1949). 163-188 (in Russian). English translation in Amer. Math. Soc. Transl. 79 (1952). Reissued in Translation Series I, 7, Algebraic Topology, American Math. Soc. (1962), 418-449.
2 P. Erdös, Graph theory and probability, II., Canad. J. Math. 13 (1961), 346-352.
3 J. H. Kim, The Ramsey number \( R(3,t)\) has order of magnitude \( t^2/ \log t\), Random Structures and Algorithms 7 (1995), 173-207.
4 P. Erdös, Some remarks on chromatic graphs, Colloq. Math. 16 (1967), 253-256.