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



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$ – Dominic van der Zypen Jun 12 '19 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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