Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i.e $\chi(G)\le C(k)$.
Using Mycielski's graphs, one can show that this number should be at least $k+\log k$.
It is known that for any integer $c$ there is a triangle-free graph that has chromatic number $c$. However in all these constructions, as far as I know, the size of these graphs is a rapidly increasing function of $c$.
I conjecture that $C(k)=\Theta(k)$ and I would be really grateful for any helpful references related to this question.