5
$\begingroup$

Let $G=(V, E)$ be the following graph:

  1. $V=\ell^\infty = $ set of bounded real sequences, with the norm $$\|x\|_\infty = \sup_{n\in\mathbb{N}}|x_n|,$$
  2. $E = \big\{\{x,y\}: x,y\in \ell^\infty \text{ and }\|x-y\|_\infty = 1\big\}$.

The unit vectors $e_i$ (defined by $e_i(n) = 1$ for $i=n$ and $e_i(n) = 0$ otherwise) form a clique, so $\chi(G) \geq \aleph_0$. But do we have $\chi(G)=\aleph_0$?

$\endgroup$

1 Answer 1

10
$\begingroup$

No. The set of all $\{0,1\}$-sequences is also a clique in $G$. Thus, $\chi(G) \geq 2^{\aleph_0}$. On the other hand, the set of all bounded real sequences has size $2^{\aleph_0}$, so $\chi(G)=2^{\aleph_0}$.

$\endgroup$

You must log in to answer this question.

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