Graphs with large palette index

DOI10.1016/J.DISC.2022.112814MaRDI QIDQ2113372zbMATH OpenOpenAlexFDO

Authors Davide Mattiolo, G. Mazzuoccolo, G. Tabarelli

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

edge-coloringpalette index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Given an edge-coloring of a graph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. We define the palette index of a graph as the minimum number of distinct palettes, taken over all edge-colorings, occurring among the vertices of the graph. Several results about the palette index of some specific classes of graphs are known. In this paper we propose a different approach that leads to new and more general results on the palette index. Our main theorem gives a sufficient condition for a graph to have palette index larger than its minimum degree. In the second part of the paper, by using such a result, we answer to two open problems on this topic. First, for every $r$ odd, we construct a family of $r$-regular graphs with palette index reaching the maximum admissible value. After that, we construct the first known family of simple graphs whose palette index grows quadratically with respect to their maximum degree.

Recommendations

• Edge-colorings of 4-regular graphs with the minimum number of palettes
• On the palette index of a graph: the case of trees
• Some results on the palette index of graphs
• A family of multigraphs with large palette index
• The total chromatic number of regular graphs of high degree
• Regular graphs with prescribed chromatic number
• The total chromatic number of regular graphs of even order and high degree
• On palette index of unicycle and bicycle graphs
• Regular graphs and edge chromatic number
• d‐Regular graphs of acyclic chromatic index at least d+2

Cites work

• A family of multigraphs with large palette index
• Edge-colorings of 4-regular graphs with the minimum number of palettes
• Minimum number of palettes in edge colorings
• On palette index of unicycle and bicycle graphs
• On the minimum number of bond-edge types and tile types: an approach by edge-colorings of graphs
• On the palette index of a graph: the case of trees
• On the palette index of complete bipartite graphs
• Some results on the palette index of graphs
• Two results on the palette index of graphs

Cited in

(9)

• On palette index of unicycle and bicycle graphs
• Two results on the palette index of graphs
• Can colour-blind distinguish colour palettes?
• Some results on the palette index of graphs
• 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 family of multigraphs with large palette index
• ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR
• On the palette index of a graph: the case of trees

This page was built for publication: Graphs with large palette index

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