Skip to main content
2 of 2
added 293 characters in body

Yes, there always is such a graph. The following construction is, I believe, due to Erdos and Hajnal.

For a cardinal $\lambda$, $[\lambda]^2$ denotes the set of all 2-element sets of ordinals less than $\lambda$ and will be thought of as the set of ordered pairs $(\alpha, \beta)$ such that $\alpha < \beta < \lambda$. Fix an infinite cardinal, $\kappa$. We define a graph $G$ whose vertex set is $[(2^\kappa)^+]^2$. Given $(\alpha, \beta), (\gamma, \delta) \in [(2^\kappa)^+]^2$, there is an edge between $(\alpha, \beta)$ and $(\gamma, \delta)$ iff $\beta = \gamma$, i.e. iff $\alpha < \beta = \gamma < \delta$. It is immediate that $G$ has no triangles. I claim that $\chi(G) > \kappa$. To see this, suppose $c:[(2^\kappa)^+]^2 \rightarrow \kappa$. By Erdos-Rado, there are $\alpha < \beta < \gamma < (2^\kappa)^+$ such that $c(\alpha, \beta) = c(\alpha, \gamma) = c(\beta, \gamma)$. But then $(\alpha, \beta)$ and $(\beta, \gamma)$ are connected by an edge in $G$ and are given the same color by $c$.

Thus, we get graphs with no triangles having arbitrarily high chromatic numbers. I originally claimed that we could get triangle-free graphs of chromatic number exactly $\kappa$ for all infinite $\kappa$ by taking subgraphs of the graphs defined above, but this is not necessarily true. There is another construction, given in Problems and Theorems in Classical Set Theory by Komjath and Totik (problem 23.24), which gives a triangle-free graph of chromatic number exactly $\kappa$.