Bounded vertex coloring of trees

A k-bounded vertex coloring of a graph G is a usual vertex coloring in which each color is applied to at most k vertices. The bounded chromatic number χk(G) is the smallest number of colors such that G admits a k-bounded coloring. In this paper, we study the problem of bounded vertex coloring of trees. We characterize the trees on n vertices that can be k-bounded colored with ⌈n/k⌉ colors. The analysis provides an efficient algorithm for determining the k-bounded chromatic number of a tree and an optimal coloring. This answers a question raised by Hansen, Hertz and Kuplinsky (Discrete Math. 111 (1993), 305).