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 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 \cite{Z} 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 \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: |