Given a proper edge coloring phi of a graph G, we define the palette S-G (v, phi) of a vertex v is an element of V(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. 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. s(G) amp;lt;= 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.
Funding Agencies|Swedish Research Council [2017-05077]