Fractional and j-Fold Coloring of the Plane

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