  A b-coloring of the vertices of a graph is a proper coloring where each color
class contains a vertex which is adjacent to at least one vertex in each other
color class. The b-chromatic number of $G$ is the maximum integer $b(G)$ for
which $G$ has a b-coloring with $b(G)$ colors. This problem was introduced by
Irving and Manlove in 1999, where they showed that computing $b(G)$ is
$\mathcal{NP}$-hard in general and polynomial-time solvable for trees. Since
then, a number of complexity results were shown, including NP-hardness results
for chordal graphs (Havet et. al., 2011) and line graphs (Campos et. al.,
2015). In this article, we present a polynomial time algorithm that solves the
problem restricted to claw-free block graphs, an important subclass of chordal
graphs and line graphs. This is equivalent to solving the edge coloring version
of the problem restricted to trees.
