Have a look here : http://www.mathlinks.ro/Forum/viewtopic.php?highlight=no+triangle&t=21943 Pierre.

I must draw your attention about the fact (not mentioned in the link above either) that there exists a much stronger result (this would be awkward in a competition, if someone invoked this result). Theorem (Erdos 1959) For every integer $ n$, there exists a graph $ G$ with girth $ g(G) > n$ and chromatic number $ \chi(G) > n$. The girth of a graph is the length of its shortest cycle ($ \infty$ for acyclic graphs), so $ g(G) > n$ prohibits not just triangles, but any cycles of length at most $ n$. The chromatic number of a graph is the minimum number of colors needed to color its vertices so that adjacent vertices bear different colors. The proof uses the Probabilistic Method (and it is unknown to me any construction-type proof). The reference is [R. Diestel - Graph Theory].

I have an idea: Consider the Ramsey number $R(3, t)$. Since there exist two constants $c_1, c_2\in \mathbb{R}^+$ such that $$c_1\dfrac{t^2}{lnt}<R(3, t)<c_2\dfrac{t^2}{lnt}$$so for any $n\in \mathbb{Z}^+$, we can find a $t$ such that $$R(3, t)>nt$$which means there exists a graph $G(V, E)$ with $|V|=nt$ such that $G$ has no triangles and independent sets with $t$ vertices. Clearly, this $G$ satisfies the condition since if it can be colored by $n$ colors it must has an independent set with no less than $t$ vertices.

Wrong...

An example of triangle-free graph with high chromatic number is called Mycielski graph.

mavropnevma wrote: I must draw your attention about the fact (not mentioned in the link above either) that there exists a much stronger result (this would be awkward in a competition, if someone invoked this result). Theorem (Erdos 1959) For every integer $ n$, there exists a graph $ G$ with girth $ g(G) > n$ and chromatic number $ \chi(G) > n.$ This result is an amazing showcase of the probabilistic method. Here is a complete proof. Theorem. For any positive integers $k$ and $\ell$ there exists a graph $G$ with chromatic number greater than $k$ which doesn't have cycles of length smaller than or equal to $\ell{}.$ Proof. We construct a graph $G$ with $n$ vertices, where each edge appears randomly and independently with probability $p$. Fix a value $\lambda\in (0,1/\ell)$ and set $p=n^{\lambda-1}$. Let $X$ be the random variable which denotes the number of cycles in $G$ with length at most $\ell$. The number of cycles of length $t$ is at most $n^t$ and each such cycle occurs with probability $p^t$. Consequently, \[\mathbb{E}[X]\leqslant 1+np+\cdots+(np)^\ell\leqslant n^{\lambda\ell}/(1-n^{-\lambda}).\]Because $\lambda\ell<1$, for sufficiently large $n$, this expected value does not exceed $n/4$. From Markov's inequality $\text{Pr}[X\geqslant n/2]\leqslant 1/2$. We will now turn our attention to the chromatic number $\chi(G)$. In order to do this, we will study the size $\alpha(G)$ of the largest independent set in $G$. Since every colour class forms an independent set, $\chi(G)\geqslant |V(G)|/\alpha(G)$. Set $a=\lceil3p^{-1}\log n\rceil$ and observe that from the union bound\[\text{Pr}[\alpha(G)\geqslant a]\leqslant\binom{n}{a}(1-p)^{\binom{a}{2}}\leqslant n^ae^{-p\binom{a}{2}}\leqslant n^{(3-a)/2}.\]Evidently, the right-most term tends to zero as $n$ tends to infinity. Consequently, for large enough $n$ this probability is at most $1/2$. By using the union bound yet again, it follows that \[\text{Pr}[X\geqslant n/2\text{ or } \alpha(G)\geqslant a]<1.\]Hence, there exists a graph with $X<n/2$ cycles of length at most $\ell$ and $\alpha(G)<a$. Now, we can simply delete one arbitrary vertex from each unsatisfactory cycle. We thus form a graph $G'$ with at least $n/2$ vertices, no cycles of length at most $\ell$ and with $\alpha(G')<a$, so \[\chi(G')\geqslant\frac{|V(G')|}{\alpha(G')}\geqslant\frac{n/2}{\frac{3}{p}\log n}=\frac{n^\lambda}{6\log n}.\]Evidently, by taking $n$ to be sufficiently large, we can ensure $\chi(G')>k$ as well, so we are done.