ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR

Author(s)

ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR Petros Petrosyan

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.

DOI: 10.46991/PYSU:A/2022.56.3.085 Physical and Mathematical Sciences, 56(3 (259) 85-96

Download PDF

Keywords

edge coloring, palette index, spanning star, complete split graph, threshold graph

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]