b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs

Flavia Bonomo, Oliver Schaudt, Maya Stein +1

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted…