  A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that
each color class contains a vertex that has at least one neighbor in all the
other color classes. The b-Coloring problem asks whether a graph $G$ has a
$b$-coloring with $k$ colors. The $b$-chromatic number of a graph $G$, denoted
by $\chi_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring
with $k$ colors. We consider the complexity of the b-Coloring problem, whenever
the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The
maximum degree $\Delta(G)$ plus one, and the $m$-degree, denoted by $m(G)$,
which is defined as the maximum number $i$ such that $G$ has $i$ vertices of
degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k
\in \{\Delta(G) + 1 - p, m(G) - p\}$, the problem is polynomial-time solvable
whenever $p \in \{0, 1\}$ and, even when $k = 3$, it is NP-complete whenever $p
\ge 2$. We furthermore consider parameterizations of the b-Coloring problem
that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two
FPT-algorithms. First, we show that deciding whether a graph $G$ has a
$b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second, we
show that b-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$, where
$\ell_k(G)$ denotes the number of vertices of degree at least $k$.
