Given an edge-coloring of a graph, the palette of a vertex is deﬁned as the set of colors of the edges which are incident with it. We deﬁne the palette index of a graph as the minimum number of distinct palettes, taken over all edge-colorings, occurring among the vertices of the graph. Several results about the palette index of some speciﬁc classes of graphs are known. In this paper we propose a different approach that leads to new and more general results on the palette index. Our main theorem gives a suﬃcient condition for a graph to have palette index larger than its minimum degree. In the second part of the paper, by using such a result, we answer to two open problems on this topic. First, for every r odd, we construct a family of r-regular graphs with palette index reaching the maximum admissible value. After that, we construct the ﬁrst known family of simple graphs whose palette index grows quadratically with respect to their maximum degree.
Graphs with large palette index / Mattiolo, D.; Mazzuoccolo, G.; Tabarelli, G.. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 345:5(2022), pp. 1-4. [10.1016/j.disc.2022.112814]