Kaleidoscopic Colorings of Graphs

Gary Chartrand ; Sean English ; Ping Zhang

Discussiones Mathematicae Graph Theory, Tome 37 (2017), p. 711-727 / Harvested from The Polish Digital Mathematics Library

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 cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (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 cm(u) ≠ cm(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 Kk+3 is a k-kaleidoscope and the complete graph Kn is a 3-kaleidoscope for each integer n ≥ 6. The largest order of an r-regular 3-kaleidoscope is [...] (r−12) $\left( {{{r - 1} \cr 2 } } \right)$ . 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) $\left( {{{r - 1} \over 2}} \right)$ .

Détail

Publié le : 2017-01-01
EUDML-ID : urn:eudml:doc:288296