<p>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. <a href="https://math.stackexchange.com/questions/167258/inequality-between-chromatic-number-and-number-of-edges-of-a-graph">here</a>, showing that a graph of size <span class="math-container">$O(k^2)$</span> has chromatic number <span class="math-container">$O(k)$</span>, which proves that <span class="math-container">$C(k) \in \Theta(k)$</span>.</p>

<p><em>EDIT: This answer is invalidated by an update to the original question.</em></p>

CC BY-SA 4.0
2020-03-03T17:22:43.560Z
2020-03-04T08:00:19.170Z
2020-03-04T08:00:19.170Z
smapers
<p>Uniformly random <span class="math-container">$k^2$</span>-vertex graphs have clique size <span class="math-container">$O(\log k)$</span>, well under <span class="math-container">$k$</span>, and independent set size also <span class="math-container">$O(\log k)$</span>, implying that their chromatic number is <span class="math-container">$\Omega(k^2/\log k)$</span>.</p>

<p>As for <span class="math-container">$k^2$</span>-vertex triangle-free graphs, their chromatic number can be <span class="math-container">$\Theta(k/\sqrt{\log k})$</span> (and not higher); see Kim, Jeong Han (1995),
"The Ramsey number <span class="math-container">$R(3,t)$</span> has order of magnitude <span class="math-container">$t^2/\log t$</span>", <em>Random Structures &amp; Algorithms</em> 7 (3): 173–207, <a href="https://doi.org/10.1002/rsa.3240070302" rel="noreferrer">doi:10.1002/rsa.3240070302</a></p>

<p>If by "size" you mean edges rather than vertices, then the maximum chromatic number of triangle-free <span class="math-container">$k^2$</span>-edge graphs is <span class="math-container">$\Theta((k/\log k)^{2/3})$</span>. See Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", <em>Discrete Mathematics</em> 211(1–3): 261–262, <a href="https://doi.org/10.1016/S0012-365X(99)00109-0" rel="noreferrer">doi:10.1016/S0012-365X(99)00109-0</a>.</p>

CC BY-SA 4.0
2020-04-20T17:26:30.217Z
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.
RJK
CC BY-SA 4.0
2020-03-03T19:47:09.723Z
2020-03-03T21:23:13.983Z
2020-03-03T21:23:13.983Z
David Eppstein
<p>Given a parameter <span class="math-container">$k$</span>, and a graph <span class="math-container">$G$</span> with <span class="math-container">$O(k^2)$</span> vertices that has a maximum clique with <span class="math-container">$\le k$</span> vertices, I want to investigate the maximum number of colors <span class="math-container">$C(k)$</span> needed to properly color <span class="math-container">$G$</span>, i.e <span class="math-container">$\chi(G)\le C(k)$</span>.</p>

<p>Using Mycielski's graphs, one can show that this number should be at least <span class="math-container">$k+\log k$</span>.</p>

<p>It is known that for any integer <span class="math-container">$c$</span> there is a triangle-free graph that has chromatic number <span class="math-container">$c$</span>. However in all these constructions, as far as I know, the size of these graphs is a rapidly increasing function of <span class="math-container">$c$</span>. </p>

<p>I conjecture that <span class="math-container">$C(k)=\Theta(k)$</span> and I would be really grateful for any helpful references related to this question.</p>

CC BY-SA 4.0
2020-03-03T17:30:20.027Z
Do you mean the size (number of edges) or the order (number of vertices) to be $O(k^2)$?
Gamow
CC BY-SA 4.0
2020-03-03T23:32:37.293Z
Sorry for the confusion, I actually meant "order". I make an edit
Mathieu Mari
<reference-request><co.combinatorics><graph-colouring><extremal-combinatorics>
On the coloring number of small graphs with small cliques
Mathieu Mari
# On the coloring number of small graphs with small cliques

(Asked by: username_0 on 2020-03-03)

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.

**Tags:** reference-request, co.combinatorics, graph-colouring, extremal-combinatorics
> **Comments:**
> **username_1**: Do you mean the size (number of edges) or the order (number of vertices) to be $O(k^2)$?  
> **username_0**: Sorry for the confusion, I actually meant "order". I make an edit  

---

## 2 answers

### Answer by username_3 on 2020-03-03. Score: 7 | Accepted answer

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](https://doi.org/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](https://doi.org/10.1016/S0012-365X(99)00109-0).

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_2 on 2020-03-03. Score: 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](https://math.stackexchange.com/questions/167258/inequality-between-chromatic-number-and-number-of-edges-of-a-graph), 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.*


---

