TWO RESULTS ON THE PALETTE INDEX OF 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-27; Published: 2025-01-27

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 palettesoccurring in a proper edge coloring ofG. A graphGis called nearly bipartite ifthere existsv∈V(G)so thatG−vis a bipartite graph. In this paper, we givean upper bound on the palette index of a nearly bipartite graphGby using thedecomposition ofGinto cycles. We also provide an upper bound on the paletteindex of Cartesian products of graphs. In particular, we show that for any graphsGandH, ˇs(GH)≤ˇs(G)ˇs(H).