Next: Jason Brown - The Up: Extremal Combinatorics / Combinatoire Previous: Richard Anstee, Ron Ferguson
Aart Blokhuis, Ralph Faudree
,
András Gyárfás and
Miklós Ruszinkó - Anti-Ramsey colorings in several rounds
| TEX2HTML_WRAP_INLINE$^$, András Gyárfás and Miklós Ruszinkó, Department of Mathematics and Computer Science, Technical University of Eindhoven; Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152, USA; Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary and Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary |
| Anti-Ramsey colorings in several rounds |
For positive integers 
and t let
denote the
minimum number of colors such that at least in one of the tcolorings
of edges of Kn all
edges of every
get different colors. Generalizing a result of Körner and Simonyi,
it
is shown in this paper that
. Also
two-round colorings in cases k>3 are investigated. Tight bounds for
for all values of k except for k=5 are obtained.
Conversely, let t(k,n) denote the minimum number of colorings such
that--having the same
colors in each coloring--at least
in one of the total t colorings of Kn all
edges of
every
get different colors. It is also shown, that
for k=n/2t(k,n) is exponentially large. Several related
questions are investigated.
Next: Jason Brown - The Up: Extremal Combinatorics / Combinatoire Previous: Richard Anstee, Ron Ferguson
