A family of multigraphs with large palette index

DOI10.26493/1855-3974.1528.D41MaRDI QIDQ5217064zbMATH OpenOpenAlexWikidataFDO

Authors Maddalena Avesani, A. Bonisoli, G. Mazzuoccolo

Publication date 21 February 2020

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

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

zbMATH Keywords

edge coloringinterval edge-coloringpalette index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

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

Cited in

(6)

• Families of pairs of graphs with a large number of common cards
• A note on one-sided interval edge colorings of bipartite graphs
• ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR
• 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

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)