Weak graph colorings
Fabian Kühn · 2009
We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min{k,deg(v)} neighbors with a different color. We show that for all d∈{1,...,Δ}, it is possible to compute a O(Δ2/d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈{1,...,Δ}, a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds.