• Aghasi B. Ghazaryan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
  • Petros A. Petrosyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia




edge coloring, palette index, spanning star, complete split graph, threshold graph


A proper edge coloring of a graph $G$ is a mapping $\alpha:E(G)\longrightarrow \mathbb{N}$ such that $\alpha(e)\not=\alpha(e')$ for every pair of adjacent edges $e$ and $e'$ in $G$. In a proper edge coloring of a graph $G$, the palette of a vertex $v \in V(G)$ is the set of colors assigned to the edges incident to $v$. The palette index of $G$ is the minimum number of distinct palettes occurring in $G$ among all proper edge colorings of $G$. A graph $G$ has a spanning star, if it has a spanning subgraph which is a star. In this paper, we consider the palette index of graphs having a spanning star. In particular, we give sharp upper and lower bounds on the palette index of these graphs. We also provide some upper and lower bounds on the palette index of the complete split and threshold graphs.


Vizing V.G. On an Estimate of the Chromatic Class of a {$p$}-graph. Diskret. Analiz 3 (1964), 25-30.

West D.B. Introduction to Graph Theory. Prentice Hall (2001), 588. https://books.google.am/books?id=TuvuAAAAMAAJ

Horňák M., Kalinowski R., et al. Minimum Number of Palettes in Edge Colorings. Graph. Comb. 30 (2014), 619-626. https://doi.org/10.1007/s00373-013-1298-8

Bonvicini S., Mazzuoccolo G. Edge-Colorings of 4-regular Graphs with the Minimum Number of Palettes. Graph. Comb. 32 (2016), 1293-1311. https://doi.org/10.1007/s00373-015-1658-7

Horňák M., Hudák J. On the Palette Index of Complete Bipartite Graphs. Discuss. Math. Graph Theory 38 (2017), 463--476. https://doi.org/10.7151/dmgt.2015

Casselgren C.J., Petrosyan P.A. Some Results on the Palette Index of Graphs. Discret. Math. Theor. Comput. Sci. 21 (2019). https://doi.org/10.23638/DMTCS-21-3-11

Bonisoli A., Bonvicini S., Mazzuoccolo G. On the Palette Index of a Graph: the Case of Trees. Lecture Notes of Seminario Interdisciplinare di Matematica 14 (2017), 49-55. http://hdl.handle.net/11380/1132584

Bonvicini S., Ferrari M.M. On the Minimum Number of Bond-edge Types and Tile Types: an Approach by Edge-colorings of Graphs. Discret. Appl. Math. 277 (2020), 1-13. https://doi.org/10.1016/j.dam.2019.09.004

Avesani M., Bonisoli A., Mazzuoccolo G. A Family of Multigraphs with Large Palette Index. ARS Mathematica Contemporanea 17 (2019), 115-124. https://doi.org/10.26493/1855-3974.1528.d41

Mattiolo D., Mazzuoccolo G., Tabarelli G. Graphs with Large Palette Index. Discrete Math. 345 (2022), 112814. https://doi.org/10.1016/j.disc.2022.112814

Leven D., Galil Z. NP Completeness of Finding the Chromatic Index of Regular Graphs. J. of Algorithms 4 (1983), 35-44.

Walters M. Rectangles as Sums of Squares. Discrete Math. 309 (2009), 2913-2921. https://doi.org/10.1016/j.disc.2008.07.028

Kenyon R. Tiling a Rectangle with the Fewest Squares. J. Comb. Theory Ser. A. 76 (1996), 272-291. https://doi.org/10.1006/jcta.1996.0104

Monaci M., dos Santos A.G. Minimum Tiling of a Rectangle by Squares. Ann. Oper. Res. 271 (2018), 831--851. https://doi.org/10.1007/s10479-017-2746-2




How to Cite

Ghazaryan, A. B., & Petrosyan, P. A. (2022). ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR. Proceedings of the YSU A: Physical and Mathematical Sciences, 56(3 (259), 85–96. https://doi.org/10.46991/PYSU:A/2022.56.3.085