Skip to main content
1 of 2

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. By taking subgraphs, we can achieve every infinite $\kappa$ as the chromatic number of a triangle-free graph.