We show that b-class="smallcaps">Chromatic Number is W[1]-hard when parameterized by the b-chromatic number, k.
When class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300927&_mathId=si149.gif&_user=111111111&_pii=S0022000016300927&_rdoc=1&_issn=00220000&md5=df97ecbd059762a303d5ad3ec086e18b" title="Click to view the MathML source">k=Δ(G)+1class="mathContainer hidden">class="mathCode">, an algorithm of running in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300927&_mathId=si6.gif&_user=111111111&_pii=S0022000016300927&_rdoc=1&_issn=00220000&md5=5164707d3d0503a8664820c15d21cad2" title="Click to view the MathML source">2O(k2logk)nO(1)class="mathContainer hidden">class="mathCode"> is provided.
An class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300927&_mathId=si214.gif&_user=111111111&_pii=S0022000016300927&_rdoc=1&_issn=00220000&md5=a98b698782a3862a0de46329a40f9e1a" title="Click to view the MathML source">O(3nn4logn)class="mathContainer hidden">class="mathCode"> time algorithm on an n-vertex graph is provided.