Solutions for two conjectures on kaleidoscopic edge-colorings

Publication date: 24 November 2016

Abstract: For an

r

-regular graph

G

, we define an edge-coloring

c

with colors from

, in such a way that any vertex of

G

is incident to 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}, c d o t s, a_{k})

, where

a_{i} (1 l e q i l e q k)

denotes the number of edges with color

i

which are incident with

v

in

G

. Then this edge-coloring

c

is called a {it

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 {it

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 [P. Zhang, A Kaleidoscopic View of Graph Colorings, Springer, New York, 2016] that for any integers

n

and

k

with

n g e q k + 3 g e q 6

, the complete graph

K_{n}

is a

k

-kaleidoscope. Then, we construct an

r

-regular

3

-kaleidoscope of order

for each integer

r g e q 7

, where

r e q u i v 3 (e x t m o d 4)

, which solves another conjecture in the same book on the maximum order for

r

-regular

3

-kaleidoscopes.

This page was built for publication: Solutions for two conjectures on kaleidoscopic edge-colorings