Geodesic
Two results on the palette index of graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 1, pp. 36-43.

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

Given a proper edge coloring $\alpha$ of a graph $G$, we define the palette $S_G(v,\alpha)$ of a vertex $v\in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $\check{s}(G)$ of $G$ is the minimum number of distinct palettes occurring in a proper edge coloring of $G$. A graph $G$ is called nearly bipartite if there exists $ v\in V(G)$ so that $G-v$ is a bipartite graph. In this paper, we give an upper bound on the palette index of a nearly bipartite graph $G$ by using the decomposition of $G$ into cycles. We also provide an upper bound on the palette index of Cartesian products of graphs. In particular, we show that for any graphs $G$ and $H$, $\check{s}(G\square H)\leq \check{s}(G)\check{s}(H)$.
Keywords: edge coloring, proper edge coloring, Cartesian product.
Mots-clés : palette, palette index 
@article{UZERU_2021_55_1_a4,
     author = {K. S. Smbatyan},
     title = {Two results on the palette index of graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {36--43},
     publisher = {mathdoc},
     volume = {55},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a4/}
}
TY  - JOUR
AU  - K. S. Smbatyan
TI  - Two results on the palette index of graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2021
SP  - 36
EP  - 43
VL  - 55
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a4/
LA  - en
ID  - UZERU_2021_55_1_a4
ER  - 
%0 Journal Article
%A K. S. Smbatyan
%T Two results on the palette index of graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2021
%P 36-43
%V 55
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a4/
%G en
%F UZERU_2021_55_1_a4
K. S. Smbatyan. Two results on the palette index of graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 1, pp. 36-43. http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a4/

[1] D. B. West, Introduction to Graph Theory, Prentice-Hall, N.J., 2001 | MR | Zbl

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

[3] M. Hornak, R. Kalinowski, M. Meszka, M. Wozniak, “Minimum Number of Palettes in Edge Colorings”, Graphs Combin., 30:3 (2014), 619–626 | DOI | MR | Zbl

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

[5] 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

[6] I. Holyer, “The NP-completeness of Some Edge-partition Problems”, SIAM J. Comput., 10 (1981), 718–720 | DOI | MR | Zbl

[7] J. Akiyama, M. Kano, Factors and Factorizations of Graphs. Proof Techniques in Factor Theory, Lect. Notes Math., 2031, Springer—Verlag, Berlin, Heidelberg, 2011, 353 pp. | DOI | MR | Zbl

[8] R. Hammack, W. Imrich, S.Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press: Taylor and Francis Group, 2011 | MR | Zbl