The @math -coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for @math -coloring running in @math rounds with probability @math in a graph with @math nodes and maximum degree @math . This implies that the @math -coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains @math colors.
@cite_24: We deterministically compute a @D+1 coloring and a maximal independent set(MIS) in time O(@D^1^ ^2^+^@Q^(^1^ ^h^)+log^*n) for @D"1"+"[email protected][email protected]^1^+^i^ ^h, where @D"j is defined as the maximal number of nodes within distance j for a node and @D:[email protected]"1. Our greedy coloring and MIS algorithms improve the state-of-the-art algorithms running in O(@D+log^*n) for a large class of graphs, i.e., graphs of (moderate) neighborhood growth with h>=36. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. Our algorithm runs in time O([email protected]+log^*n) for @[email protected][email protected](log^1^+^1^ ^l^o^g^^^*^nn) and @[email protected]?O(@D log^1^+^1^ ^l^o^g^^^*^nn). For graphs of polylogarithmic chromatic number the analysis reveals an exponential gap compared to the fastest @D+1 coloring algorithm running in time O([email protected]+logn). The algorithm works without knowledge of @g and uses less than @D colors, i.e., (1-1 O(@g))@D with high probability. To the best of our knowledge this is the first distributed algorithm for (such) general graphs taking the chromatic number @g into account. We also improve on the state of the art deterministic computation of (2,c)-ruling sets.
@cite_27: The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into a single node has low chromatic number. They present an efficient distributed algorithm for constructing such a decomposition and demonstrate its use for design of efficient distributed algorithms. The method yields new deterministic distributed algorithms for finding a maximal independent set in an arbitrary graph and for ( Delta +1)-coloring of graphs with maximum degree Delta . These algorithms run in O(n sup epsilon ) time for epsilon =O((log log n log n) sup 1 2 ), whereas the best previously known deterministic algorithms required Omega (n) time. The techniques can also be used to remove randomness from the previously known most distributed breadth-first search algorithm. >
@cite_13: 
A generalization of MIS, known as an , has also been considered. A ( @math )-ruling set @math is a set of vertices such that two nodes @math have distance at least @math and for any node @math there exists a node @math with distance at most @math @cite_27 . MIS is a special case, namely a @math -ruling set. A number of papers @cite_13 @cite_24 @cite_27 use ruling sets to compute colorings in different kinds of graphs. A ruling set can be viewed as defining a network decomposition, such that any component has diameter at least @math and at most @math .