A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Woźniak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs.

Edge-colorings of 4-regular graphs with the minimum number of palettes / Bonvicini, Simona; Mazzuoccolo, G.. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - STAMPA. - 32:4(2016), pp. 1293-1311. [10.1007/s00373-015-1658-7]

Edge-colorings of 4-regular graphs with the minimum number of palettes

BONVICINI, Simona;Mazzuoccolo, G.
2016

Abstract

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Woźniak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs.
2016
32
4
1293
1311
Edge-colorings of 4-regular graphs with the minimum number of palettes / Bonvicini, Simona; Mazzuoccolo, G.. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - STAMPA. - 32:4(2016), pp. 1293-1311. [10.1007/s00373-015-1658-7]
Bonvicini, Simona; Mazzuoccolo, G.
File in questo prodotto:
File Dimensione Formato  
palette_4regular_final_version.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 227.88 kB
Formato Adobe PDF
227.88 kB Adobe PDF Visualizza/Apri
VOR_Edge-Colorings of 4-Regular Graphs.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 828.72 kB
Formato Adobe PDF
828.72 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
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/1102906
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact