On the palette index of a graph: the case of trees

The palette of a vertex v of a graph G in a proper edge-coloring is the set of colors assigned to the edges which are incident with v. The palette index of G is the minimum number of palettes occurring among all proper edge-colorings of G. After reviewing some results on the palette index of regular graphs, we consider the problem of determining the palette index for non-regular graphs. We begin by considering the family of trees. We give an upper bound for the palette index of a tree in terms of the maximum degree Δ. We show that this bound is best possible by producing, for each Δ≥ 3, a tree T^ Δ whose palette index reaches the upper bound.