Monochromatic covers in edge-colored graphs and hypergraphs

Graphs, Hypergraphs, and Computing

06 May 15:30 - 16:30

Gabor Sarkozy - Worcester Polytechnic Institute

We survey some results on the following problem:
Say we are given fixed positive integers s, t and a family of graphs F. Minimizing over all t-edge colorings of the complete graph on n vertices, we ask for the maximum number of vertices that can be covered by at most s monochromatic members of F. This problem unites two classical problems: at one end of the spectrum (s = 1) we have the Ramsey problem, while at the other end we have cover problems. But there are some interesting problems "in-between" as well.

Several of the results are joint with András Gyárfás and/or Endre Szemerédi
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to