Kaleidoscopic Colorings of Graphs

Gary Chartrand, Sean English, and Ping Zhang. "Kaleidoscopic Colorings of Graphs." Discussiones Mathematicae Graph Theory 37.3 (2017): 711-727. <http://eudml.org/doc/288296>.

@article{GaryChartrand2017,
abstract = {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)$ .},
author = {Gary Chartrand, Sean English, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge coloring; vertex coloring; kaleidoscopic coloring; kaleidoscope},
language = {eng},
number = {3},
pages = {711-727},
title = {Kaleidoscopic Colorings of Graphs},
url = {http://eudml.org/doc/288296},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Gary Chartrand
AU - Sean English
AU - Ping Zhang
TI - Kaleidoscopic Colorings of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 711
EP - 727
AB - 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)$ .
LA - eng
KW - edge coloring; vertex coloring; kaleidoscopic coloring; kaleidoscope
UR - http://eudml.org/doc/288296
ER -