TWO RESULTS ON THE PALETTE INDEX OF GRAPHS Khachik Smbatyan
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).
DOI: 10.46991/PYSU:A/2021.55.1.036 Physical and Mathematical Sciences, 55(1 (254) 36-43
