$b$-Coloring Parameterized by Pathwidth is {XNLP}-complete

We show that the $b$-Coloring problem is complete for the class XNLP whenparameterized by the pathwidth of the input graph. Besides determining theprecise parameterized complexity of this problem, this implies that b-Coloringparameterized by pathwidth is $W[t]$-hard for all $t$, and resolves theparameterized complexity of $b$-Coloring parameterized by treewidth.