Geodesic
The palette index of Sierpi\'nski triangle graphs and Sierpi\'nski graphs
Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 99-108.

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

The palette of a vertex $v$ of a graph $G$ in a proper edge coloring is the set of colors assigned to the edges which are incident to $v$. The palette index of $G$ is the minimum number of palettes occurring among all proper edge colorings of $G$. In this paper, we consider the palette index of Sierpiński graphs $S_p^n$ and Sierpiński triangle graphs $\widehat{S}_3^n$. In particular, we determine the exact value of the palette index of Sierpiński triangle graphs. We also determine the palette index of Sierpiński graphs $S_p^n$ where $p$ is even, $p=3$, or $n=2$ and $p=4l+3$.
Keywords: Sierpiński triangle graph, Sierpiński graph.
Mots-clés : palette index 
@article{PDM_2021_4_a4,
     author = {A. Ghazaryan},
     title = {The palette index of {Sierpi\'nski} triangle graphs and {Sierpi\'nski} graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {99--108},
     publisher = {mathdoc},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2021_4_a4/}
}
TY  - JOUR
AU  - A. Ghazaryan
TI  - The palette index of Sierpi\'nski triangle graphs and Sierpi\'nski graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2021
SP  - 99
EP  - 108
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2021_4_a4/
LA  - en
ID  - PDM_2021_4_a4
ER  - 
%0 Journal Article
%A A. Ghazaryan
%T The palette index of Sierpi\'nski triangle graphs and Sierpi\'nski graphs
%J Prikladnaâ diskretnaâ matematika
%D 2021
%P 99-108
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2021_4_a4/
%G en
%F PDM_2021_4_a4
A. Ghazaryan. The palette index of Sierpi\'nski triangle graphs and Sierpi\'nski graphs. Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 99-108. http://geodesic.mathdoc.fr/item/PDM_2021_4_a4/

[1] West D., Introduction to Graph Theory, Prentice-Hall, 2014 | MR

[2] Horňák M., Kalinowski R., Meszka M., Woźniak M., “Minimum number of palettes in edge colorings”, Graphs Combin., 30 (2014), 619–626 | DOI | MR | Zbl

[3] Bonvicini S. and Mazzuoccolo G., “Edge-colorings of 4-regular graphs with the minimum number of palettes”, Graphs Combin., 32 (2016), 1293–1311 | DOI | MR | Zbl

[4] Holyer I., “The NP-completeness of edge-coloring”, Siam J. Comput., 10 (1981), 718–720 | DOI | MR | Zbl

[5] Avesani M., Bonisoli A., Mazzuoccolo G., “A family of multigraphs with large palette index”, Ars Math. Contemp., 17 (2019), 115–124 | DOI | MR | Zbl

[6] Horňák M., Hudák J., “On the palette index of complete bipartite graphs”, Discussiones Mathematicae Graph Theory, 38 (2018), 463–476 | DOI | MR | Zbl

[7] Casselgren C., Petrosyan P., “Some results on the palette index of graphs”, Discrete Math. Theor. Comput. Sci., 21:3 (2019), A2 | MR

[8] 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 | MR | Zbl

[9] Klavžar S., Milutinović U., “Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem”, Czechoslovak Math. J., 47:122 (1997), 95–104 | MR | Zbl

[10] Scorer R., Grundy P., Smith C., “Some binary games”, Math. Gaz., 28 (1944), 96–103 | DOI

[11] Hinz A., Klavžar S., Zemljič S., “A survey and classification of Sierpiński-type graphs”, Discrete Math., 217:3 (2017), 565–600 | DOI | MR | Zbl

[12] Klavžar S., “Coloring Sierpiński graphs and Sierpiński triangle graphs”, Taiwan J. Math., 12 (2008), 513–522 | MR | Zbl

[13] Jakovac M., Klavžar S., “Vertex-, edge-, and total-colorings of Sierpiński-like graphs”, Discrete Math., 309:6 (2009), 1548–1556 | DOI | MR | Zbl

[14] Teguia A., Godbole A., “Sierpiński triangle graphs and some of their properties”, Australas. J. Combin., 35 (2006), 181–192 | MR | Zbl

[15] Hinz A. and Schief A., “The average distance on the Sierpiński gasket”, Probab. Theory Related Fields, 87 (1990), 129–138 | DOI | MR | Zbl

[16] Kaimanovich V., “Random walks on Sierpiński graphs: hyperbolicity and stochastic homogenization”, Fractals in Graz 2001, Trends in Mathematics, eds. P. Grabner, W. Woess, Birkhäuser, Basel, 2003, 145–183 | MR | Zbl

[17] Imran M., Hafi S., Gao W., Farahani M. R., “On topological properties of Sierpiński networks”, Chaos Soliton. Fract., 98 (2017), 199–204 | DOI | MR | Zbl