We show that b-Chromatic Number is W[1]-hard when parameterized by the b-chromatic number, k.

When k=Δ(G)+1$k=\mathrm{\Delta }(G)+1$, an algorithm of running in 2^O(k2log⁡k)n^O(1)$2^{\mathcal{O}(k^2\log k)}{n}^{\mathcal{O}(1)}$ is provided.

An O(3ⁿn⁴log⁡n)$\mathcal{O}(3^n{n}^4\log n)$ time algorithm on an n-vertex graph is provided.