Abstract:
Given a proper edge coloring $\phi$ of a graph $G$, we define the palette $S_G(v,\phi)$ of a vertex $v \in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $cyc(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 $\Delta(G)$ of $G$. We also give a sharp upper bound for the palette index of unicycle and bicycle graphs.
Fulltext:
PDF file (377 kB)