Anti-Ramsey number of edge-disjoint rainbow spanning trees

Abstract: An edge-colored graph

G

is called rainbow if every edge of

G

receives a different color. The anti-Ramsey number of

t

edge-disjoint rainbow spanning trees, denoted by

r (n, t)

, is defined as the maximum number of colors in an edge-coloring of

K_{n}

containing no

t

edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 2014] conjectured that for any fixed

t

,

whenever

n g e q 2 t + 2 g e q 6

. In this paper, we prove this conjecture. We also determine

r (n, t)

when

n = 2 t + 1

. Together with previous results, this gives the anti-Ramsey number of

t

edge-disjoint rainbow spanning trees for all values of

n

and

t

.

Recommendations

Cites Work

Cited In (6)

This page was built for publication: Anti-Ramsey number of edge-disjoint rainbow spanning trees