Distributed algorithms for fractional coloring

Description

In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It is known that for every real $\alpha>1$ and integer $\Delta$, a fractional coloring of total weight at most $\alpha(\Delta+1)$ can be obtained deterministically in a single round in graphs of maximum degree $\Delta$, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colourings with a weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. Moreover, we improve on classical bounds on the chromatic number by considering the fractional chromatic number instead, without significantly increasing the output size and the round complexity of the existing algorithms.

Abstract

12 pages, 2 figures

Abstract

International audience

Additional details