Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs

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 $\mathrm{\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 \{\mathrm{\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 $\mathrm{\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 $\mathrm{\Delta }(G)$. Second, we show that $b$-Coloring is FPT parameterized by $\mathrm{\Delta }(G)+{\ell }_k(G)$, where ${\ell }_k(G)$ denotes the number of vertices of degree at least $k$.
This is joint work with Paloma T. Lima.