ON PALETTE INDEX OF UNICYCLE AND BICYCLE GRAPHS

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Submitted: 2025-01-30; Published: 2025-01-30

This work is licensed under Creative Commons Attribution–NonCommercial International License (CC BY-NC 4.0).

Abstract

Given a proper edge coloringφof a graphG, we define the paletteSG(v,φ)of a vertexv∈V(G)as the set of all colors appearing on edges incident withv.The palette index ˇs(G)ofGis the minimum number of distinct palettes occur-ring in a proper edge coloring ofG. In this paper we give an upper bound onthe palette index of a graphGin terms of cyclomatic numbercyc(G)ofGandmaximum degree∆(G)ofG. We also give a sharp upper bound for the paletteindex of unicycle and bicycle graphs.