Some Results on Palette Index of Cartesian Product Graphs


  • Khachik S. Smbatyan Yerevan State University



Edge coloring, Proper edge coloring, Palette, Palette index, Cartesian product, Windmill graph


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.


D.B. West, “Introduction to Graph Theory“, N.J.: Prentice-Hall, 2001.

M. Horňák, R. Kalinowski, M. Meszka and M. Wózniak, “Minimum number of palettes in edge colorings“, Graphs and Combinatorics, vol. 30, pp. 619–626, 2014.

S. Bonvicini and G. Mazzuoccolo, “Edge-colorings of 4-regular graphs with the minimum number of palettes“, Graphs and Combinatorics, vol. 32, pp. 1293–1311, 2016.

I. Holyer, “The NP-completeness of edge-coloring“, SIAM Journal on Computing, vol. 10, pp. 718–720, 1981.

M. Avesani, A. Bonisoli and G. Mazzuoccolo, “A family of multigraphs with large palette index“, Ars Mathematica Contemporanea, vol. 17, pp. 115–124, 2019.

C. J. Casselgren and P. A. Petrosyan, “Some results on the palette index of graphs“, Discrete Mathematics and Theoretical Computer Science, vol. 21, no. 3.

S. Fiorini and R.J. Wilson, “Edge-Colorings of Graphs“, Research Notes in Mathematics, vol. 16, Pitman, London, UK, 1977.

R. Hammack, W. Imrich, S. Klavˇzar, Handbook of Product Graphs Second Edition, CRC Press, 2011.

V. G. Vizing, “On an estimate of the chromatic class of a p-graph“, Diskret. Analiz 3, pp. 25–30, 1964.




How to Cite

Smbatyan, K. S. (2021). Some Results on Palette Index of Cartesian Product Graphs. Mathematical Problems of Computer Science, 55, 26–34.