# Chromatic number of the linear graph on $[\omega]^\omega$

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

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.

• Wonderfully short argument, thanks @bullet51! – Dominic van der Zypen Jun 12 at 11:34