  We provide a polynomial-time algorithm for b-Coloring on graphs of constant
clique-width. This unifies and extends nearly all previously known polynomial
time results on graph classes, and answers open questions posed by Campos and
Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This
constitutes the first result concerning structural parameterizations of this
problem. We show that the problem is FPT when parameterized by the vertex cover
number on general graphs, and on chordal graphs when parameterized by the
number of colors. Additionally, we observe that our algorithm for graphs of
bounded clique-width can be adapted to solve the Fall Coloring problem within
the same runtime bound. The running times of the clique-width based algorithms
for b-Coloring and Fall Coloring are tight under the Exponential Time
Hypothesis.
