-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$
  • 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$ – Benoît Kloeckner Apr 26 '16 at 10:03
6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This assumes the axiom of choice, which should be mentioned given the dependency of related problems to the chosen axioms. $\endgroup$ – Benoît Kloeckner Apr 26 '16 at 10:05

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.