The b-chromatic number of a graph G, χb(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-CHROMATIC NUMBER problem, the objective is to decide whether χb(G)≥k. Testing whether χb(G)=Δ(G)+1, where Δ(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvíl, Tuza and Voigt, WG 2002). We show that b-CHROMATIC NUMBER is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Δ(G)+1, we design an algorithm for b-CHROMATIC NUMBER running in time 2°(k2log⁡k)n°(1). Finally, we show that b-CHROMATIC NUMBER for an n-vertex graph can be solved in time O(3nn4log⁡n). © 2016 Elsevier Inc.