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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
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
palette_4regular_final_version.pdf

Open access

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

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 828.72 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1102906`