# On the coloring number of small graphs with small cliques

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.

• Do you mean the size (number of edges) or the order (number of vertices) to be $O(k^2)$? – Gamow Mar 3 '20 at 17:30
• Sorry for the confusion, I actually meant "order". I make an edit – Mathieu Mari Mar 3 '20 at 23:32

Uniformly random $$k^2$$-vertex graphs have clique size $$O(\log k)$$, well under $$k$$, and independent set size also $$O(\log k)$$, implying that their chromatic number is $$\Omega(k^2/\log k)$$.
As for $$k^2$$-vertex triangle-free graphs, their chromatic number can be $$\Theta(k/\sqrt{\log k})$$ (and not higher); see Kim, Jeong Han (1995), "The Ramsey number $$R(3,t)$$ has order of magnitude $$t^2/\log t$$", Random Structures & Algorithms 7 (3): 173–207, doi:10.1002/rsa.3240070302
If by "size" you mean edges rather than vertices, then the maximum chromatic number of triangle-free $$k^2$$-edge graphs is $$\Theta((k/\log k)^{2/3})$$. See Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", Discrete Mathematics 211(1–3): 261–262, doi:10.1016/S0012-365X(99)00109-0.
In addition to the Mycielski graphs, I guess you only need an upper bound on the chromatic number, as a function of the graph size. Such a bound is mentioned e.g. here, showing that a graph of size $$O(k^2)$$ has chromatic number $$O(k)$$, which proves that $$C(k) \in \Theta(k)$$.