ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR
DOI:
https://doi.org/10.46991/PYSU:A/2022.56.3.085Keywords:
edge coloring, palette index, spanning star, complete split graph, threshold graphAbstract
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.
References
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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
