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 $v\in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $\check{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 $ v\in V(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$, $\check{s}(G\square H)≤ \check{s}(G)\check{s}(H)$.
Keywords: edge coloring; proper edge coloring; palette; palette index; Cartesian product