Some Results on Palette Index of Cartesian Product Graphs

Given a proper edge coloring α of a graph G, we define the palette SG(ν, α) of a vertex ν ∈ V (G) as the set of all colors appearing on edges incident to ν. The palette index š(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. The windmill graph Wd(n, k) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared universal vertex. In this paper, we determine the bound on the palette index of Cartesian products of complete graphs and simple paths. We also consider the problem of determining the palette index of windmill graphs. In particular, we show that for any positive integers n, k ≥ 2, š(Wd(n, 2k)) = n + 1.

Abstract licence: CC BY-NC

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.