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 '20 at 17:30
  • $\begingroup$ Sorry for the confusion, I actually meant "order". I make an edit $\endgroup$ – 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.

  • $\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 '20 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, privacy policy and cookie policy

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