What's the largest constant $c >1$ such that all triangle free graphs with chromatic number $n$ has atleast $\Theta(c^n) $ vertices?

## 1 Answer

It follows from the result in A note on Ramsey numbers by M. Ajtai, J. Komlós, E. Szemerédi that a triangle free graph on $s$ vertices has chromatic number at most $\Theta(\sqrt\frac{s}{\log s})$.

Moreover, in The Ramsey Number $R(3, t)$ has Order of Magnitude $t^2/\log t$, Kim proves that this is optimal by exhibiting triangle free graphs on $s$ vertices with chromatic number equal to that bound. This means that if a triangle free graph has chromatic number $n$,as in the question, its number of vertices can be as low as $\Theta(n^2\log n)$ which is not exponential in $n$, as the question suggests.