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]

### Graphs with large palette index

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2022
345
5
1
4
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]
Mattiolo, D.; Mazzuoccolo, G.; Tabarelli, G.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1310852`
• ND
• 1
• 1