On vertex b-critical trees

Abstract

A b-coloring is a proper coloring of the vertices of a graph such that each color class has a vertex that has neighbors of all other colors. The b-chromatic number of a graph $G$ is the largest $k$ such that $G$ admits a b-coloring with $k$ colors. A graph $G$ is b-critical if the removal of any vertex of $G$ decreases the b-chromatic number. We prove various properties of b-critical trees. In particular, we characterize b-critical trees.