9
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ For $\chi(G)=\aleph_0$ you can just take an infinite disjoint union of graphs $G_n$ such that $\chi(G_n)=n$ and $\omega(G_n)=2$. $\endgroup$ May 20, 2015 at 10:19
  • 1
    $\begingroup$ Yes, See this: renyi.hu/~p_erdos/1959-19.pdf $\endgroup$
    – Ashutosh
    May 20, 2015 at 12:53

2 Answers 2

18
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ $~$Very elegant! $\endgroup$
    – Ashutosh
    May 20, 2015 at 13:00
  • $\begingroup$ Yes - very well written - unfortunately I was only able to up-vote once.. $\endgroup$
    – user70876
    May 20, 2015 at 13:10
  • 3
    $\begingroup$ Here's the reference to the stronger result mentioned by Chris: renyi.hu/~p_erdos/1960-01.pdf $\endgroup$
    – Ashutosh
    May 20, 2015 at 13:16
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.