ON PALETTE INDEX OF UNICYCLE AND BICYCLE GRAPHS - Ghazaryan, A.B. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2019)
Given a proper edge coloring $ φ $ of a graph $ G $, we define the palette $ S_G ( u, φ) $ of a vertex $ u \mathclose{\in} V(G) $ as the set of all colors appearing on edges incident with $ u $. The palette index $ \check{s} (G) $ of $ G $ is the minimum number of distinct palettes occurring in a proper edge coloring of $ G $. In this paper we give an upper bound on the palette index of a graph G in terms of cyclomatic number $ cyc(G) $ of $ G $ and maximum degree $ Δ (G) $ of $ G $. We also give a sharp upper bound for the palette index of unicycle and bicycle graphs.
Keywords: palette; edge coloring; unicycle graph; bicycle graph