4
$\begingroup$

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

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.