Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model

Dan Hefetz, Fabian Kuhn, Yannic Maus +1

We show an $\Omega \left({\Delta }^{\frac{1}{3}-\frac{\eta }{3}}\right)$ lower bound on the runtime of any deterministic distributed $\mathcal{O}\left({\Delta }^{1+\eta }\right)$-graph coloring algorithm in a weak vari…