Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally

Jan Bok, Avinandan Das, Anna Gujgiczer +1

We investigate the classical and distributed complexity of \emph{$k$-partial $c$-coloring} where $c=k$, a natural generalization of Brooks' theorem where each vertex should be colo…