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).
No institution available
Mathematics
, 2025, Issue 1, pp. 1–10
ISSN Online: 0000-0000
DOI:
10.xxxx/example-doi