Authors:
X. Li, X. Zhu
Title:
Kaleidoscopic edge-coloring of complete graphs and r-regular graphs
Source:
Discussiones Mathematicae Graph Theory
Received 18.04.2017, Revised 16.12.2017, Accepted 16.12.2017, doi: 10.7151/dmgt.2107

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 \cite{Z} 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 \binom{r-1}{2}-1 for each integer r≥ 7, where r≡ 3\ (\text{mod}\ 4), which solves another conjecture in \cite{Z} on the maximum order of r-regular 3-kaleidoscopes.
Keywords:
k-kaleidoscope, regular graph, edge-coloring

Links:
PDF