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.

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

2 Answers 2


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.

  • $\begingroup$ To add to this, for David's third comment, it was actually Poljak and Tuza (1994) who first showed this (modulo Kim's result): S. Poljak and Z. Tuza. Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math., 7(2):307–313, 1994. Moreover, Gimbel and Thomassen (2000) were contemporaneous to Noga: J. Gimbel and C. Thomassen. Coloring triangle-free graphs with fixed size. Discrete Math., 219(1-3):275–277, 2000. $\endgroup$
    – RJK
    Apr 20, 2020 at 17:26

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

EDIT: This answer is invalidated by an update to the original question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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