Skip to main content
1 of 3

Conflict-free coloring of $\mathbb{R}$ with the Euclidean topology

A hypergraph $H =(V, E)$ consists of a set $V$ and a set $E \subseteq {\cal P}(V)$ of subsets of $V$. A hypergraph coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal and the restriction $c\restriction_e: e \to \kappa$ is non-constant whenever $e$ has more than $1$ element. The chromatic number $\chi(H)$ is the least cardinal $\kappa \neq \emptyset$ such that there is a coloring $c: V \to \kappa$.

The map $c:V\to \kappa$ is said to be a conflict-free if every (non-empty) edge $e\in E$ contains at least one vertex $v$ of a color unique in $e$, or more formally, if there is $v\in e$ such that $$e \;\cap\; \big(c^{-1}(\{c(v)\})\big) = \{v\}.$$ The conflict-free chromatic number $\chi_{\text{cf}}(H)$ is the least cardinal $\kappa \neq \emptyset$ such that there is a conflict-free coloring $c: V \to \kappa$.

(Conflict-free colorings were motivated by a frequency assignment problem in cellular networks, see the introduction of this article.)

Let $\tau$ be the Euclidean topology on $\mathbb{R}$. The chromatic number $\chi(\mathbb{R}, \tau)$ equals $2$.

Question. What is $\chi_{\text{cf}}(\mathbb{R},\tau)$?