Edge-b-coloring Trees

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 in 1999, where they showed that computing $b(G)$ is $\mathcal{NP}$-hard in general and polynomial-time solvable for trees. Since then, a number of complexity results were shown, including NP-hardness results for chordal graphs (Havet et. al., 2011) and line graphs (Campos et. al., 2015). In this article, we present a polynomial time algorithm that solves the problem restricted to claw-free block graphs, an important subclass of chordal graphs and line graphs. This is equivalent to solving the edge coloring version of the problem restricted to trees.

No reviews yet.

No comments yet.