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

Abstract

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 cm(v) of a vertex v is defined as the ordered tuple (a1, a2, . . . , ak), where ai (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 Kn 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 Kn is a k-kaleidoscope. Then, we construct an r-regular 3-kaleidoscope of order ( 2r-1)-1$\left( {_{\,\,\,2}^{r - 1}} \right) - 1$ − 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
• 05c15