What are the definitions of countable and measurable colourings of a graph?

In this paper, the author discusses colourings of the plane, or in other words, of the underlying graph. I suppose a finite colouring is a colouring using at most $$k$$ colours for some natural number $$k$$. However, what do countable and measurable colourings mean? Does the former perhaps mean that any vertex of the graph can get associated with a (potentially unbounded) natural number representing its colour? I have no clue what measurable colourings may be though.

A countable colouring of the plane $$\mathbb{R}^2$$ is just a function $$c : \mathbb{R}^2 \to \mathbb{N}$$, meaning we have countably many distinct colours available to us.

The notion of measurable colouring is a bit ambiguous, it could mean either Borel-measurable or Lebesgue-measurable. A colouring $$c : \mathbb{R}^2 \to \mathbf{k}$$ or $$c : \mathbb{R}^2 \to \mathbb{N}$$ is called Borel/Lebesgue-measurable, if each fibre $$c^{-1}(n)$$ is a Borel respectively Lebesgue-measurable subset of $$\mathbb{R}^2$$.

An example of a Borel-measurable colouring is taking finitely many lines in $$\mathbb{R}^2$$, and giving a distinct colour to each resulting component, while giving yet another colour to the lines itself.

Examples for non-Borel-measurable colouring will be weird. For example, take the Cantor middle third set $$C$$, and give everything in $$\mathbb{R}^2 \setminus C \times \{0\}$$ colour $$0$$. Identify each $$x \in C \times \{0\}$$ first with the corresponding $$x' \in 2^\mathbb{N}$$, and then view $$x'$$ as coding a tree $$T_x \subseteq \mathbb{N}^{<\omega}$$. Now colour $$x$$ by $$1$$ iff $$T_x$$ is well-founded, and by $$2$$ otherwise.

• Shouldn't $\mathbf{k}$ be $[k]$? Also, would it be possible to give an example of a colouring which is (and/or one which isn't) Borel-measurable? Oct 28, 2022 at 15:20
• @J.Schmidt I'm using $\mathbf{k} = \{0,1,\ldots,k-1\}$. I've added examples, although I don't think examples are useful here.
– Arno
Oct 28, 2022 at 16:33
• That non-Borel-measurable colouring example is incomprehensible for me, but thanks for trying. Oct 29, 2022 at 17:39

I suppose those are mathematics terms (since the considered graph is infinite).

Countable means you can count those colorings with integers (there is a bijection with $$\mathbb{N}$$).

Measurable means you can quantify those with a certain notion.

• To be more precise concerning countable colorings, would it be the colors of the vertices which are in bijection with $\mathbb{N}$? Concerning measurable colorings, I still don't have a clue on which colorings would be considered measurable and which wouldn't... Oct 28, 2022 at 13:34
• No, I think it is the set of colorings that is countable, not the coloring itself. For the measurability, I don't really know, I haven't really read the paper. Oct 28, 2022 at 13:37
• @Nathaniel It's definitely the set of colours, not the set of colourings, which is countable.
– Arno
Oct 28, 2022 at 14:13