Constructing a triangle-free $k$-chromatic graph I am working on some problems related to coloring on graphs, and I ran into
a problem that may need some graph induction, which I am not too familiar with.
For every $k \in \mathbb{N}$, I need to construct a triangle-free
$k$-chromatic graph.
For $k = 1$ and $k=2$, these can be trivially $K_1$ and $K_2$ respectively.
What gets somewhat peculiar is when we attempt to build this graph for
$k = 3$ and $k = 4$. For $k = 3$, My original
thought was to construct a graph where all
vertices are adjacent to one particular vertex and the rest of the vertices
being adjacent as such:
$$V(G) = \{v_1,v_2,v_3,v_4,v_5\}$$
$$E(G) = \{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_1\},\{v_5,v_i\}
\forall i \in [4]\}.$$
However, I seem to have left myself again with several odd cycles of length
$3$. Is there potentially a way I can find this for $k = 3$ using an
induced subgraph of this graph? Beyond that, what may be a useful way to
use graph induction to solve a problem like this?
 A: 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.

A creative approach may be to consider an infinite graph with vertices labelled with $1,2,3,\ldots$ and arcs between labels whose difference is an integer cube. By the case $n=3$ of FLT, such graph is triangle-free. By using some deep results in additive combinatorics (in particular, a variation of Sarkozy's theorem) it can be shown that the chromatic number of such graph is $+\infty$. By combinatorial compactness, it follows that there are (finite) triangle-free graphs with arbitrary chromatic number.

