-1
$\begingroup$

In the setting of the Hadwiger-Nelson problem, two points of $\mathbb{R}^2$ form an edge if and only if their distance is $1$. The resulting graph $G$ has chromatic number $\chi(G)\in \{4,5,6,7\}$ and has uncountably many connected components.

If we take $S\subseteq \mathbb{R}^2$ and regard it as an induced subgraph of $\mathbb{R}^2$ with the edge set described above such that $\chi(S)=\chi(G)$, does it follow that $|S|=\frak{c}$?

$\endgroup$
1
  • 2
    $\begingroup$ The graph $G$ is connected (e.g. any two points can be connected by a chain of length $2$ if they are at distance $<1$). Despite the accepted answer, your question still makes sense in axiomatic theories without choice. $\endgroup$ Apr 26, 2016 at 10:03

1 Answer 1

6
$\begingroup$

No. There is a finite $S$ with the same chromatic number. See this.

$\endgroup$
1
  • 2
    $\begingroup$ This assumes the axiom of choice, which should be mentioned given the dependency of related problems to the chosen axioms. $\endgroup$ Apr 26, 2016 at 10:05

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.