Greedy-Like Defective Coloring: Distributed Algorithms and Applications
2026-08-03 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study a way to color graph nodes so that each node has only a few neighbors with the same color, called defective coloring. They improve a known two-step method that assigns colors to nodes efficiently in distributed systems, and they extend it to a more flexible version called list defective coloring. This leads to a new algorithm for proper coloring using around the number of colors equal to the maximum degree plus one, running efficiently in a distributed model. They also show that by choosing the number of colors carefully (not a perfect square), the defect can be slightly improved, but there is a limit to how low the defect can go with their method.
graph coloringdefective coloringdistributed algorithmslist coloringmaximum degree Δtwo-pass greedy algorithmCONGEST modelproper coloringcolor defectdistributed complexity
Authors
Marc Fuchs, Fabian Kuhn
Abstract
A $d$-defective $c$-coloring of a graph $G=(V,E)$ is a coloring of the nodes $V$ with $c$ colors such that every node has at most $d$ neighbors of the same color. Distributed algorithms for computing different variants of defective coloring are at the core of most deterministic state-of-the-art distributed coloring algorithms, and they are also an important tool in many other distributed graph algorithms. In several cases, the overall complexity could be improved if some version of defective coloring could be solved more efficiently. Barenboim and Elkin [STOC '09] introduced a two-pass greedy algorithm that uses $p^2$ colors with defect $\lfloor Δ/p\rfloor$ in $O(Δ+\log^{\ast} n)$ rounds. This remains the best defect/color tradeoff for $O(\log^{\ast} n)$-time algorithms in bounded-degree graphs. This paper expands the capabilities of this two-pass algorithm. First, we generalize it to the \emph{list defective coloring} problem (Fuchs and Kuhn, [DISC '23]). Consequently, we obtain an alternative algorithm for computing a proper $(Δ+1)$-coloring in $\tilde{O}(\sqrtΔ) + O(\log^{\ast} n)$ rounds in the CONGEST model. Second, we analyze a generalized two-pass algorithm for standard defective colorings. We prove that if the number of colors $c$ is not a perfect square, we can improve the state-of-the-art defect for distributed $c$-colorings by a constant factor in most cases. However, we also prove a limitation: for any $c\geq 1$, this generalized algorithm cannot achieve a $c$-coloring with defect below $(1-o(1))\cdotΔ/\sqrt{c}$.