Kaleidoscopic Colorings of Graphs

Chartrand, Gary ; English, Sean ; Zhang, Ping

Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 711-727

Résumé

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.

Détail

Keywords: edge coloring, vertex coloring, kaleidoscopic coloring, kaleidoscope