Given an infinite cardinal $\kappa$, is there a graph $G$ that has no clique consisting of more than 2 points, but $\chi(G) = \kappa$?



Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$
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$.


