Some results on the palette index of graphs

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 $\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 various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $\check{s}(G)\le 1+\max \{a,b\}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.

Cited by in corpus (1)

• A characterization of graphs with small palette index