2
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes.

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .