Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$

Question

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

Answer 1

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$.

Answer 2

Let me make a note of the countable case. Given a finite triangle-free graph, a simple and elegant Mycielski's construction provides a finite triangle-free graph which has chromatic number larger by $1$. A disjoint union of an increasing sequence of such graphs provides a countable triangle-free graph which has infinite chromatic number.

For Mycielski's construction see:

    https://en.wikipedia.org/wiki/Mycielskian