Geodesic
On the palette index of graphs having a spanning star
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 3, pp. 85-96.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: edge coloring, spanning star, complete split graph, threshold graph.
Mots-clés : palette index 
@article{UZERU_2022_56_3_a0,
     author = {A. {\CYRV}. Ghazaryan and P. A. Petrosyan},
     title = {On the palette index of graphs having a spanning star},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {85--96},
     publisher = {mathdoc},
     volume = {56},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2022_56_3_a0/}
}
TY  - JOUR
AU  - A. В. Ghazaryan
AU  - P. A. Petrosyan
TI  - On the palette index of graphs having a spanning star
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2022
SP  - 85
EP  - 96
VL  - 56
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2022_56_3_a0/
LA  - en
ID  - UZERU_2022_56_3_a0
ER  - 
%0 Journal Article
%A A. В. Ghazaryan
%A P. A. Petrosyan
%T On the palette index of graphs having a spanning star
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2022
%P 85-96
%V 56
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2022_56_3_a0/
%G en
%F UZERU_2022_56_3_a0
A. В. Ghazaryan; P. A. Petrosyan. On the palette index of graphs having a spanning star. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 3, pp. 85-96. http://geodesic.mathdoc.fr/item/UZERU_2022_56_3_a0/

[1] V. Vizing, “On an Estimate of the Chromatic Class of a $p$-graph”, Diskretny Analiz, 3 (1964), 25–30 (in Russian) | MR

[2] D. B. West, Introduction to Graph Theory, Pearson Education Inc., 2001, 588 pp. https://books.google.am/books?id=TuvuAAAAMAAJ

[3] M. Horňák, R. Kalinowski, M. Meszka, M. Woźniak, “Minimum Number of Palettes in Edge Colorings”, Graphs Combin., 30 (2014), 619–626 | DOI | MR | Zbl

[4] S. Bonvicini, G. Mazzuoccolo, “Edge-colorings of 4-regular Graphs with the Minimum Number of Palettes”, Graphs Combin., 32 (2016), 1293–1311 | DOI | MR | Zbl

[5] M. Horňák, J. Hudák, “On the Palette Index of Complete Bipartite Graphs”, Discuss. Math. Graph Theory, 38 (2017), 463–476 | DOI | MR

[6] C. J. Casselgren, P. A. Petrosyan, “Some Results on the Palette Index of Graphs”, Discrete Mathematics and Theoretical Computer Science, 2019 | DOI | MR | Zbl

[7] A. Bonisoli, S. Bonvicini, G. Mazzuoccolo, “On the Palette Index of a Graph: The Case of Trees”, Lecture Notes of Seminario Interdisciplinare di Matematica, 14 (2017), 49–55 | MR | Zbl

[8] S. Bonvicini, M. M. Ferrari, “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 | DOI | MR | Zbl

[9] M. Avesani, A. Bonisoli, G. Mazzuoccolo, “A Family of Multigraphs with Large Palette Index”, Ars Math. Contemp., 17 (2019), 115–124 | DOI | MR | Zbl

[10] D. Mattiolo, G. Mazzuoccolo, G. Tabarelli, “Graphs with Large Palette Index”, Discrete Math., 345 (2022), 112814 | DOI | MR | Zbl

[11] D. Leven, Z. Galil, “$NP$ Completeness of Finding the Chromatic Index of Regular Graphs”, J. Algorithms, 4 (1983), 35–44 | DOI | MR | Zbl

[12] M. Walters, “Rectangles as Sums of Squares”, Discrete Math., 309 (2009), 2913–2921 | DOI | MR | Zbl

[13] R. Kenyon, “Tiling a Rectangle with the Fewest Squares”, J. Comb. Theory Ser. A., 76 (1996), 272–291 | DOI | MR | Zbl

[14] M. Monaci, A. G. dos Santos, “Minimum Tiling of a Rectangle by Squares”, Ann. Oper. Res., 271 (2018), 831–851 | DOI | MR | Zbl