Fractional Chromatic Number

Section 47.2 Fractional Chromatic Number

Definition 47.2.1.

For a given graph $G=(V,E)$ and the positive integers $m$ and $n\text{,}$ $m\leq n\text{,}$ a proper $n/m$ -colouring with $n$ colours of the graph $G$ is a function that assigns to each vertex a set of $m$ distinct colours, in such a way that adjacent vertices are assigned mutually disjoint sets.

The fractional chromatic number of $G$ is defined as

$\begin{equation*} \chi_f(G)=\inf\left\{\frac{n}{m}: \mbox{there is a proper } n/m \mbox{ colouring of }G\right\}. \end{equation*}$

Let $m$ and $n$ be positive integers with $m \leq n\text{.}$ An $n/m$ -colouring is a function with $n$ colours of the plane that assigns a set of $m$ distinct colours to each point in the plane so that any two points that are one unit apart are assigned mutually disjoint sets.

The fractional chromatic number of the plane is:

$\begin{equation*} \chi_{f} (\mathbb{R}^2) = \inf\left\{ \frac{n}{m}: \text{there is a proper n/m colouring of the plane}\right\} . \end{equation*}$

🔗

The current lower bound for the fractional chromatic number of the plane,

$\chi_{f} (\mathbb{R}^2) \geq \frac{1999983}{512933} \approx 3.8991\text{,}$ was established in 2020 by Bellitto, Pêcher, and Sédillot, and the upper bound,

$4.3599\text{,}$ was established in 1993 by Hochberg and O'Donnell.

🔗

Example 47.2.2.

The Moser spindle ($MS$) is used to establish an early lower bound of the chromatic number of the plane. Four colours are required to colour the vertices, so that no two adjacent vertices are of the same colour.

We can apply the definition of the fractional colouring to the above fact to establish that $\chi_f(MS)\leq 4/1=4\text{.}$

Figure 47.2.3. A $4/1$-fractional colouring of the vertices of the Moser spindle.

But can we do better? If we place three colours in each vertex, we find that we only need eleven colours to colour the Moser spindle. Which gives us a $\chi_f (MS)\leq \frac{11}{3}\approx 3.66\text{.}$

Figure 47.2.4. A graph isomorphic to the Moser spindle together with its proper $11/3$ colouring

In fact, it is known that the fractional chromatic number of the Moserr spindle is 3.5. This is because the Moser spindle has 7 vertices and the independence number 2. This was first observed in 1992 by David Fisher and Daniel Ullman.

Figure 47.2.5. A graph isomorphic to the Moser spindle together with its proper $7/2$ colouring

Observe that the fact that $\chi_f(MS)=3.5$ implies that $\chi_f(\mathbb{R}^2)\geq 3.5\text{.}$

🔗

$\textbf{References:}$

🔗

Bellitto, T., Pêcher, A., and Sédillot, A. (2020). On the density of sets of the Euclidean plane avoiding distance 1. https://arxiv.org/abs/1810.00960

🔗

Cranston, D. W., Rabern, L. (2017). The fractional chromatic number of the plane. Combinatorica. 37(5): 837-861.

🔗

Hochberg, R., O'Donnell, P. (1993). A large independent set in the unit distance graph. Geombinatorics. 2(4):83-84.

🔗

D. Fisher and D. Ullman. (1992). The fractional chromatic number of the plane. Geombinatorics, 2(1):8-12.