Geodesic
Kaleidoscopic Edge-Coloring of Complete Graphs and r-Regular Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 881-888

Voir la notice de l'article provenant de la source Library of Science

For an r-regular graph G, we define an edge-coloring c with colors from 1, 2, . . ., k, in such a way that any vertex of G is incident with at least one edge of each color. The multiset-color c_m(v) of a vertex v is defined as the ordered tuple (a_1, a_2, . . ., a_k), where a_i (1 ≤ i ≤ k) denotes the number of edges of color i which are incident with v in G. Then this edge-coloring c is called a k-kaleidoscopic coloring of G if every two distinct vertices in G have different multiset-colors and in this way the graph G is defined as a k-kaleidoscope. In this paper, we determine the integer k for a complete graph K_n to be a k-kaleidoscope, and hence solve a conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] that for any integers n and k with n ≥ k + 3 ≥ 6, the complete graph K_n is a k-kaleidoscope. Then, we construct an r-regular 3-kaleidoscope of order r-12 - 1 for each integer r ≥ 7, where r ≡ 3 (mod 4), which solves another conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] on the maximum order of r-regular 3-kaleidoscopes.
Keywords: k -kaleidoscope, regular graph, edge-coloring 
Li, Xueliang; Zhu, Xiaoyu. Kaleidoscopic Edge-Coloring of Complete Graphs and r-Regular Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 881-888. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a8/
@article{DMGT_2019_39_4_a8,
     author = {Li, Xueliang and Zhu, Xiaoyu},
     title = {Kaleidoscopic {Edge-Coloring} of {Complete} {Graphs} and {r-Regular} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {881--888},
     year = {2019},
     volume = {39},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a8/}
}
TY  - JOUR
AU  - Li, Xueliang
AU  - Zhu, Xiaoyu
TI  - Kaleidoscopic Edge-Coloring of Complete Graphs and r-Regular Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 881
EP  - 888
VL  - 39
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a8/
LA  - en
ID  - DMGT_2019_39_4_a8
ER  - 
%0 Journal Article
%A Li, Xueliang
%A Zhu, Xiaoyu
%T Kaleidoscopic Edge-Coloring of Complete Graphs and r-Regular Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 881-888
%V 39
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a8/
%G en
%F DMGT_2019_39_4_a8

[1] J.A. Bondy, U.S.R. Murty, Graph Theory (Springer, 2008).

[2] G. Chartrand, S. English and P. Zhang, Kaleidoscopic colorings of graphs, Discuss. Math. Graph Theory 37 (2017) 711–727. doi:10.7151/dmgt.1950

[3] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.

[4] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1–38. doi:10.1007/s00373-012-1243-2

[5] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Math., Springer, New York, 2012).

[6] P. Zhang, A Kaleidoscopic View of Graph Colorings (Springer Briefs in Math., New York, 2016). doi:10.1007/978-3-319-30518-9