TWO RESULTS ON THE PALETTE INDEX OF GRAPHS - Smbatyan, Khachik S. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2021)
Given a proper edge coloring α of a graph G, we define the palette S_G(v,α) of a vertex vV(G) as the set of all colors appearing on edges incident with v. The palette index s(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. A graph G is called nearly bipartite if there exists vV(G) so that G-v is a bipartite graph. In this paper, we give an upper bound on the palette index of a nearly bipartite graph G by using the decomposition of G into cycles. We also provide an upper bound on the palette index of Cartesian products of graphs. In particular, we show that for any graphs G and H, s(GH)≤ s(G)s(H).