Geodesic
On the palette index of unicycle and bicycle graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 53 (2019) no. 1, pp. 3-12.

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

Given a proper edge coloring $\phi$ of a graph $G$, we define the palette $S_G(v,\phi)$ of a vertex $v \in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $cyc(G)$ of $G$ is the minimum number of distinct palettes occurring in a proper edge coloring of $G$. In this paper we give an upper bound on the palette index of a graph $G$, in terms of cyclomatic number $cyc(G)$ of $G$ and maximum degree $\Delta(G)$ of $G$. We also give a sharp upper bound for the palette index of unicycle and bicycle graphs.
Keywords: edge coloring, bicycle graph.
Mots-clés : Palette, unicycle graph 
@article{UZERU_2019_53_1_a0,
     author = {A. V. Ghazaryan},
     title = {On the palette index of unicycle and bicycle graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {3--12},
     publisher = {mathdoc},
     volume = {53},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2019_53_1_a0/}
}
TY  - JOUR
AU  - A. V. Ghazaryan
TI  - On the palette index of unicycle and bicycle graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2019
SP  - 3
EP  - 12
VL  - 53
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2019_53_1_a0/
LA  - en
ID  - UZERU_2019_53_1_a0
ER  - 
%0 Journal Article
%A A. V. Ghazaryan
%T On the palette index of unicycle and bicycle graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2019
%P 3-12
%V 53
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2019_53_1_a0/
%G en
%F UZERU_2019_53_1_a0
A. V. Ghazaryan. On the palette index of unicycle and bicycle graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 53 (2019) no. 1, pp. 3-12. http://geodesic.mathdoc.fr/item/UZERU_2019_53_1_a0/

[1] D. B. West, Introduction to Graph Theory, Prentice-Hall, New Delhi, 2003 | MR | Zbl

[2] X. Zhu, “Circular Chromatic Number of Planar Graphs of Large Odd Girth”, Electronic J. of Combinatorics, 8:1 (2001), Research Paper 25, 11 pp. | MR | Zbl

[3] V. G. Vizing, “Coloring the Vertices of a Graph in Prescribed Colors”, Diskret. Analiz, Novosibirsk, 29 (1976), 3–10 | MR | Zbl

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

[5] S. Fiorini, R. J Wilson, Edge-Colorings of Graphs, Pitman, London, 1977 | MR | Zbl

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

[7] I. Holyer, “The NP-Completeness of Some Edge-Partition Problems”, SIAM J. Comput., 10 (1981), 713–717 | DOI | MR | Zbl

[8] M. Avesani, A. Bonisoli, G. Mazzuoccolo, A Family of Multigraphs with Large Palette Index, 2018, arXiv: 1801.01336v1 [math.CO]

[9] M. Hornak, J. Hudak, “On the Palette Index of Complete Bipartite Graphs”, Discussiones Mathematicae Graph Theory, 38 (2018), 463–476 | DOI | MR | Zbl

[10] C. J. Casselgren, P. A. Petrosyan, “Some Results on the Palette Index of Graphs”, Discrete Mathematics and Theoretical Computer Science, 2019 (to appear) | Zbl

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