# 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$$.

Bibliography
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.