Geodesic
Kaleidoscopic Colorings of Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 711-727.

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

For an r-regular graph G, let c : E(G) → [k] = 1, 2, . . ., k, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color c_m(v) of v is defined as the ordered k-tuple (a_1, a_2, . . ., a_k) or a_1a_2…a_k, where a_i (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if c_m(u) c_m(v) for every two distinct vertices u and v of G. A regular graph G is called a k-kaleidoscope if G has a k-kaleidoscopic coloring. It is shown that for each integer k ≥ 3, the complete graph K_k+3 is a k-kaleidoscope and the complete graph K_n is a 3-kaleidoscope for each integer n ≥ 6. The largest order of an r-regular 3-kaleidoscope is r-12. It is shown that for each integer r ≥ 5 such that r ≢3 (mod 4), there exists an r-regular 3-kaleidoscope of order r-12.
Keywords: edge coloring, vertex coloring, kaleidoscopic coloring, kaleidoscope 
@article{DMGT_2017_37_3_a14,
     author = {Chartrand, Gary and English, Sean and Zhang, Ping},
     title = {Kaleidoscopic {Colorings} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {711--727},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a14/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - English, Sean
AU  - Zhang, Ping
TI  - Kaleidoscopic Colorings of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 711
EP  - 727
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a14/
LA  - en
ID  - DMGT_2017_37_3_a14
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A English, Sean
%A Zhang, Ping
%T Kaleidoscopic Colorings of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 711-727
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a14/
%G en
%F DMGT_2017_37_3_a14
Chartrand, Gary; English, Sean; Zhang, Ping. Kaleidoscopic Colorings of Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 711-727. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a14/

[1] M. Aigner, E. Triesch and Zs. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, Combinatorics’ 90 Elsevier Science Pub., New York (1992) 1–9.

[2] A C. Burris and R.H. Schelp, Vertex-distinguishing proper edge colorings, J. Graph Theory 26 (1997) 73–82. doi:10.1002/(SICI)1097-0118(199710)26:2〈73::AID-JGT2〉3.0.CO;2-C

[3] J. Černý, M. Horňák and R. Soták, Observability of a graph, Math. Slovaca 46 (1996) 21–31.

[4] G. Chartrand. S. English and P. Zhang, Binomial colorings of graphs, Bull. Inst. Combin. Appl. 76 (2016) 69–84.

[5] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, Boca Raton, FL, 2009).

[6] O. Favaron, H. Li and R. H. Schelp, Strong edge colorings of graphs, Discrete Math. 159 (1996) 103–109. doi:10.1016/0012-365X(95)00102-3

[7] P.G. Tait, Remarks on the colouring of maps, Proc. Royal Soc. Edinburgh 10 (1880) 501–503, 729. doi:10.1017/S0370164600044643