Distributed Testing of Distance-k Colorings

We study the distributed decision problem related to checking distance-k coloring, defined as color assignments to the nodes such that every pair of vertices at distance at most k must receive distinct colors. While checking the validity of a distance-k coloring only requires \(\lceil k/2\rceil \) rounds in the Local model, and a single round in the Congest model when \(k\le 2\), the task is extremely costly for higher k’s in Congest—there is a lower bound of \(\varOmega (\varDelta ^{k/2})\) rounds in graphs with maximum degree \(\varDelta \). We therefore explore the ability of checking distance-k coloring via distributed property testing. We consider several farness criteria for measuring the distance to a valid coloring, and we derive upper and lower bounds for each of them. In particular, we show that for one natural farness measure, significantly better algorithms are possible for testing distance-3 coloring than for testing distance-k coloring for \(k \ge 4\).