Kaleidoscopic Edge-Coloring of Complete Graphs and r-Regular Graphs

Li, Xueliang ; Zhu, Xiaoyu

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 881-888

Résumé

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.

Détail

Keywords: k -kaleidoscope, regular graph, edge-coloring