A family of multigraphs with large palette index

Authors

  • Maddalena Avesani Università di Verona, Italy
  • Arrigo Bonisoli Università di Modena e Reggio Emilia, Italy
  • Giuseppe Mazzuoccolo Università di Verona, Italy

DOI:

https://doi.org/10.26493/1855-3974.1528.d41

Keywords:

Palette index, edge-coloring, interval edge-coloring

Abstract

Given a proper edge-coloring of a loopless multigraph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. The palette index of a multigraph is defined as the minimum number of distinct palettes occurring among the vertices, taken over all proper edge-colorings of the multigraph itself. In this framework, the palette pseudograph of an edge-colored multigraph is defined in this paper and some of its properties are investigated. We show that these properties can be applied in a natural way in order to produce the first known family of multigraphs whose palette index is expressed in terms of the maximum degree by a quadratic polynomial. We also attempt an analysis of our result in connection with some related questions.

Author Biographies

Arrigo Bonisoli, Università di Modena e Reggio Emilia, Italy

Full Professore - Dipartimento di Scienze Fisiche, Informatiche e Matematiche

Giuseppe Mazzuoccolo, Università di Verona, Italy

Associate Professor - Department of Computer Science

Downloads

Published

2019-08-25

Issue

Vol. 17 No. 1 (2019)

Section

Articles

License

Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/