A family of multigraphs with large palette index

DOI10.26493/1855-3974.1528.D41zbMATH Open1433.05111arXiv1801.01336OpenAlexW2969561551WikidataQ127315142 ScholiaQ127315142MaRDI QIDQ5217064FDOQ5217064

Authors: Maddalena Avesani, A. Bonisoli, G. Mazzuoccolo 

Publication date: 21 February 2020

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

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 multigraph 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.

Full work available at URL: https://arxiv.org/abs/1801.01336

Recommendations

• Graphs with large palette index
• On the palette index of a graph: the case of trees
• ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR
• On the palette index of complete bipartite graphs
• On palette index of unicycle and bicycle graphs

zbMATH Keywords

edge coloringinterval edge-coloringpalette index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory
• A dynamic survey of graph labeling
• Compact cyclic edge-colorings of graphs
• Compact Cylindrical Chromatic Scheduling
• 1-Factorizations of cartesian products of regular graphs
• Interval colorings of edges of a multigraph
• Title not available (Why is that?)
• On the palette index of complete bipartite graphs
• Minimum number of palettes in edge colorings
• Edge-colorings of 4-regular graphs with the minimum number of palettes
• On the palette index of a graph: the case of trees

Cited In (6)

• Graphs with large palette index
• The palette index of Sierpiński triangle graphs and Sierpiński graphs
• Edge-colorings of 4-regular graphs with the minimum number of palettes
• A note on one-sided interval edge colorings of bipartite graphs
• ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR
• Families of pairs of graphs with a large number of common cards

This page was built for publication: A family of multigraphs with large palette index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217064)