The b-chromatic index of graphs

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to at least one vertex in each other color class. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors. This problem was introduced by Irving and Manlove (1999), where they showed that computing b(G) is NP-hard in general and polynomial-time solvable for trees. A natural question that arises is whether the edge version of this problem is also NP-hard or not. Here, we prove that computing the b-chromatic index of a graph G is NP-hard, even if G is either a comparability graph or a Ck-free graph, and give partial results on the complexity of the problem restricted to trees, more specifically, we solve the problem for caterpillars graphs. Although solving problems on caterpillar graphs is usually quite simple, this problem revealed itself to be unusually hard. The presented algorithm uses a dynamic programming approach that combines partial solutions which are proved to exist if, and only if, a particular polyhedron is non-empty.