From a k-chromatic triangle free graph G lets construct a k+1 chromatic triangle free graph G'. Let X(G) be the chromatic number of G. Let V(G)= {v1,...,vn}. Beginning with G add vertices X={x1,...,xn} and one more vertex y. Add edges to make x_i adjacent to all of N(v_i), and let N(y)= X. Clearly X is an idependet set in G'. Hence the other vertices of any triangle containing x_i belong to V(G) and are neighbors of v_i. This would complete a triangle in G, which can't exist. Therefore G' is triangle free. A proper k-coloring f of G extends to a proper k+1 coloring of G' by setting f(x_i)=f(v_i) and f(y)=k+1. Therefore X(G')<=X(G) + 1. So to obtain equality we show that X(G) < X(G'). So we consider any proper coloring of G' and obain from it a proper coloring of G using fewer colors. Let g be a proper k-coloring of G'. By changing the names of colors we may assume that g(y)=k. This restricts g to {1,...,k-1} on X. In V(G), it may use all k colors. Let A be the set of vertices in G on which g uses color k; we change the colors used on A to obain a proper k-1 coloring of G. For each v_1 in A we change the color of v_1 to g(x_i). Because all the vertices in A have color k under g, no two vertices of A are adjacent. Thus we need only check edges of the form v_i,v' with v_i in A and v' in V(G) - A. If v' is adjacent to v_i then by construction also v' is adjacent to x_i, which yields that g(v') and g(x_i) are different. Since we change the color on v_i to g(x_i) our change does not violate the edge v_i,v'. So the modified coloring of V(G) is a proper k-1 coloring of G.

Very nice!!!

My solution is different : Let $k=2^n$, let's consider the grid of the points of the plane with integer and positive coordinates. Let $\Delta_i$ be the line with equation $x=i$, where $i=1,...,k$. Now consider the graph whose vertices are the grid points where $1 \leq a,b \leq k$. And join $(a,b)$ and $(c,d)$ by an edge iff $a+b=c$ or $c+d = a$, that is join $(a,b)$ to all the points of the line $\Delta_{a+b}$ and only to them. Assume that $(a,b),(c,d),(e,f)$ form a triangle. Wlog, we may assume that $a \leq c \leq e$. In that case $a+b=c=e$ and $c+d=e$, which forces $d=0$, a contradiction. Thus, there is no triangle. Now, let $a,b$ be two positive integers both not greater than $k$, and assume that $a<b$. It follows that the point $(a,b-a)$ is joined to $(b,y)$, for all $y$, so that each point of the line $\Delta_b$ must have a color distinct from the color of $(a,b-a).$ It follows that the set of colors determined by $\Delta_a$ is distinct from the set of colors of $\Delta_b$. Thus, we must have at least $2^n$ pairwise distinct available sets of colors, and clearly none is the empty set. It follows that the number of available colors is greater than $n$, and we are done. Pierre.