Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$. Let $$E = \{\{a,b\}: a,b\in [\omega]^\omega\text{ and } |a\cap b| = 1\}.$$ It is clear that $G = ([\omega]^\omega, E)$ has no uncountable cliques, but do we also have $\chi(G) = \aleph_0$?


1 Answer 1



Take the two smallest elements of a vertex $V\in[\omega]^\omega$ as its color. The number of colors is $\aleph_0$, and any two vertices with the same color shares at least two elements, so they are not connected.

  • $\begingroup$ Wonderfully short argument, thanks @bullet51! $\endgroup$ Commented Jun 12, 2019 at 11:34

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.