2009/08/11 by Fabian Kühn · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research #Combinatorics #Graph #Edge coloring #Mathematics #Fractional coloring #Graph coloring #Greedy coloring #Complete coloring #Degree (music) #Chromatic scale #Discrete mathematics #List coloring #Binary logarithm #Graph power #Line graph #Physics
paper · doi:10.1145/1583991.1584032
openalex publication_date 2009/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 mink,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.