A note on approximating the bb-chromatic number

We consider the problem of approximating the bb-chromatic number of a graph. In 2005, Corteel et al. proved that there is no constant ϵ>0ϵ>0 for which this problem can be approximated within a factor of 120/113−ϵ120/113−ϵ in polynomial time, unless P=NPP=NP. An existence of a constant-factor approximation algorithm for the bb-chromatic number in general graphs was formulated as an open problem.In this paper we settle this question in a negative way proving that there is no constant ϵ>0ϵ>0, for which the problem can be approximated within a factor n1/4−ϵn1/4−ϵ, unless P=NPP=NP.