Skip to main content
3 of 3
Name of article and MO question
LSpice
  • 12.9k
  • 4
  • 45
  • 69

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\; \bigl(c^{-1}(\{c(v)\})\bigr) = \{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 Pach and Tardos - Conflict-free colorings of graphs and hypergraphs.)

Of course, every conflict-free coloring is a coloring in the "traditional" sense, so $\chi(H) \leq \chi_{\text{cf}}(H)$.

Let $\tau$ be the Euclidean topology on $\mathbb{R}$. The chromatic number $\chi(\mathbb{R}, \tau)$ equals $2$ (see Chromatic number of a connected Hausdorff space).

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