On edge-b-critical graphs ?
A b-coloring  of a graph G G is a proper coloring of the vertices of G G such that in each color class there exists a vertex having neighbors in all the other color classes. The b-chromatic number b(G) b ( G ) of a graph G G is the largest integer such that G G admits a b-coloring with k k colors. A graph G G is edge b-critical if deleting any edge decreases its b-chromatic number. We characterize the class of P5 P 5 -free graphs, d d -regular graphs and trees which are edge b-critical. As a consequence we show that deciding if a graph is edge-b-critical is NP-hard.
b-coloring b-chromatic number edge b-critical graph