On edge-b-critical graphs

A b-coloring   of a graph GG is a proper coloring of the vertices of GG 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 GG is the largest integer such that GG admits a b-coloring with kk colors. A graph GG is edge b-critical if deleting any edge decreases its b-chromatic number. We characterize the class of P5P5-free graphs, dd-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.