ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR

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-21; Published: 2025-01-21

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

Abstract

A proper edge coloring of a graph G is a mapping α:E(G)⟶N such that α(e)≠α(e′) for every pair of adjacent edges e and e′ in G. In a proper edge coloring of a graph G, the palette of a vertex v∈V(G) is the set of colors assigned to the edges incident to v. The palette index of G is the minimum number of distinct palettes occurring in G among all proper edge colorings of G. A graph G has a spanning star, if it has a spanning subgraph which is a star. In this paper, we consider the palette index of graphs having a spanning star. In particular, we give sharp upper and lower bounds on the palette index of these graphs. We also provide some upper and lower bounds on the palette index of the complete split and threshold graphs.