Fractional and $j$-fold colouring of the plane

Abstract

We present results referring to the Hadwiger-Nelson problem which asks for the minimum number of colours needed to colour the plane with no two points at distance $1$ having the same colour. Exoo considered a more general problem concerning graphs $G_{[a,b]}$ with ${\mathbb{R}}^2$ as the vertex set and two vertices adjacent if their distance is in the interval $[a,b]$. Exoo conjectured $\chi (G_{[a,b]})=7$ for sufficiently small but positive difference between $a$ and $b$. We partially answer this conjecture by proving that $\chi (G_{[a,b]})\ge 5$ for $b>a$. A $j$-fold colouring of graph $G=(V,E)$ is an assignment of $j$-elemental sets of colours to the vertices of $G$, in such a way that the sets assigned to any two adjacent vertices are disjoint. The fractional chromatic number ${\chi }_f(G)$ is the infimum of fractions $k/j$ for $j$-fold colouring of $G$ using $k$ colours. We generalize a method by Hochberg and O'Donnel (who proved that $G_{[1,1]}\le 4.36$) for fractional colouring of graphs $G_{[a,b]}$, obtaining a bound dependant on $\frac{a}{b}$. We also present few specific and two general methods for $j$-fold coloring of $G_{[a,b]}$ for small $j$, in particular for $G_{[1,1]}$ and $G_{[1,2]}$. The $j$-fold colouring for small $j$ has strong practical motivation especially in scheduling theory, while graph $G_{[1,2]}$ is often used to model hidden conflicts in radio networks.

Cited by in corpus (1)

• On the cromatic number of infinitesimal plane layer