Graphs with large palette index

DOI10.1016/J.DISC.2022.112814zbMATH Open1490.05079arXiv2107.03827OpenAlexW3178034339MaRDI QIDQ2113372FDOQ2113372

Authors: Davide Mattiolo, G. Mazzuoccolo, G. Tabarelli 

Publication date: 14 March 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

edge-coloringpalette index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Some results on the palette index of graphs
• 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
• TWO RESULTS ON THE PALETTE INDEX OF GRAPHS
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the minimum number of bond-edge types and tile types: an approach by edge-colorings of graphs
• A family of multigraphs with large palette index

Cited In (2)

• Edge-colorings of 4-regular graphs with the minimum number of palettes
• ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR

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)