Brief Announcement: Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
Marc Fuchs, Fabian Kühn · 2024
In this paper, we give list coloring variants of simple iterative defective coloring algorithms. Formally, in a list defective coloring instance, each node υ of a graph is given a list Lυ of colors and a list of allowed defects dυ(x) for the colors. Each node υ needs to be colored with a color x ∈ Lυ such that at most dυ(x) neighbors (or outneighbors) of υ also pick the same color x.