The following is probably not the slickest way, but here it is anyway. Note that there are some details I'm leaving for you to fill in. Of course whenever I say "coloring," I always mean a proper coloring.
For a graph $G$, let $\Delta(G)$ denote the maximum degree amongst all the vertices in $G$. Recall the following famous result.
Brook's Theorem: Let $G$ be a connected graph. If $G$ is either a cycle of odd length or a complete graph, then $\chi(G)=\Delta(G)+1$. Otherwise, $\chi(G)\leq \Delta(G)$.
Next, convince yourself of the following.
Lemma: If $H$ is a triangle-free graph on $5$ or fewer vertices, then either $H$ is a cycle of length $5$ or $\chi(H)\leq 2$.
So now suppose you are given a triangle-free graph $G$ on $10$ or fewer vertices. We may as well assume that $G$ is connected and has at least $6$ vertices. Furthermore, we can assume that $\Delta(G)\geq 4$.
Let $v$ be a vertex of degree $\Delta(G)$, let $A$ be the neighbours of $v$. Note that $A$ is an independent set (i.e, no edges exist between vertices in $A$). Let $B$ be the subgraph induced by the non-neighbours of $v$.
If $\Delta(G)>4$, then $B$ has at most $4$ vertices. By the lemma, the vertices of $B$ can then be colored using two colors, say red and blue. Next, we can color all vertices of $A$ green. Finally, since $v$ is not adjacent to any vertex in $B$, we can color it red. Thus we've found a $3$-coloring of $G$.
If $\Delta(G)=4$, and $B$ is not a cycle of length $5$, then proceed as in the previous paragraph to obtain a $3$-coloring of $G$. So we may now assume that $\Delta(G)=4$ and that $B$ is a cycle of length $5$. Note that this means $G$ has $10$ vertices. In particular, we now know that any triangle-free graph on at most $9$ vertices is $3$-colorable.
Now, if any vertex $w$ in $G$ has $\deg(w)\leq 2$, delete it. The resulting graph $G-w$ has $9$ vertices and so we can color it with three colors. But since the deleted vertex has at most two neighbours in $G$, this means that such a coloring of $G-w$ can be extended to a coloring of $G$ using three colors, and we're done. So now assume all vertices in $G$ have degree at least $3$. Since $G$ is triangle-free, this means that every vertex in $A$ has exactly two neighbours in $B$. So at this point, $G$ looks like:
Suppose a vertex in $b\in B$ is adjacent to all four neighbours in $A$. Since there are no vertices of degree $2$, the two neighbours of $b$ are also adjacent to a vertex in $A$. But then $G$ would not be triangle-free, so no vertex in $B$ can be adjacent to all four vertices in $A$.
Suppose a vertex $b\in B$ has exactly three neighbours in $A$. This forces the two neighbours of $b$ in $B$ to be adjacent to the fourth vertex in $A$, and the neighbours of $b$ in $A$ to be adjacent to one of the two non-neighbours of $b$ in $B$. In a thousand words, $G$ looks like:
But now we can $3$-color $G$ as so:
Finally, we may suppose no vertex in $B$ has more than two neighbours in $A$. But since there are $8$ edges between $A$ and $B$, this means that exactly three vertices in $B$ have two neighbours in $A$. Hence two of these vertices must be adjacent, and so the graph looks like:
Color the vertices as so:
But since $G$ is triangle-free, this is actually a proper $3$-coloring.
For a cycle graph $C_n$ with even $n$, for convenience, denote the set of vertices as $\{v_1, v_2, \cdots, v_n\}$ and without loss of generality, let the set of edges be $\{(v_1, v_2), (v_2, v_3), \cdots, (v_{n-1}, v_n), (v_n, v_1)\}$.
First, observe that $\{v_1, v_3, \cdots, v_{n-1}\}$ is of size $\frac{n}{2}$ and it is an independent set. Therefore, the size of the maximum independent set, denoted as $\alpha(C_n)$, is at least $\frac{n}{2}$. Now suppose that $\alpha(C_n) > \frac{n}{2}$. Since each vertex is of degree $2$ and vertices in an independent set share no edge, we conclude that there are at least $\alpha(C_n) \cdot 2 > n$, which is a contradiction.
Best Answer
The Mycielskian is what you need.
The given construction proves that by starting with a triangle-free graph on $5$ vertices with $\chi(G)=3$, we may get a triangle-free graph on $11$ vertices with $\chi(G)=4$, then a triangle-free graph on $23$ vertices with $\chi(G)=5$, then a triangle-free graph on $47$ vertices with $\chi(G)=6$ and so on.
Actually, the minimum number of vertices for a triangle-free graph with $\chi(G)=5$ is $22$ and not $23$, but that is another story.
Another approach to the original question is to exploit the fact that the Kneser graph $$ \text{KG}(3c-4,c-1) $$ is triangle-free and has chromatic number $c$. It has a huge number of vertices, however.