Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.

A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \implies c(u)\neq c(v)$. Intuitively, this is a valid coloring for $G^{\le 2}$.

Finally, assume that the degree of each vertex is bounded by $\Delta$.

A known result is that one can color $G$ using $\Delta^2$ colors in $O(\log^* n)$ rounds. As the degree in $G^{\le 2}$ is bounded by $\Delta^2$, it would make sense to try to color it (and thus, compute a 2-hop coloring for $G$) using $\Delta^4$ colors.

However, simulating each iteration of the coloring algorithm may require $\Omega(\Delta)$ communication rounds in the CONGEST model (as we are allowed to communicate only on $E$).

Is there an algorithm that computes a 2-hop coloring for $G$, using $\text{poly}(\Delta)$ colors, with a runtime independent or sublinear in $\Delta$? What about $k$-hop coloring for some $k=O(1)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.