Parallel (Δ+1)-coloring of constant-degree graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. Hajnal and Szemerédi proved that every graph with maximum degree Δ is equitably k-colorable for every k ≥ Δ + 1. Chen, Lih, ...

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...

Consider a graph G consisting of a vertex set V(G) and an edge set E(G). Let @D(G) and @g(G) denote the maximum degree and the chromatic number of G, respectively. We say that G is equitably @D(G)-colorable if there exists a proper @D(G)-coloring of G ...