Rainbow numbers for matchings and complete graphs Original Research Article

For a given graph H and n⩾1, let f(n,H) denote the maximum number m for which it is possible to colour the edges of the complete graph Kn with m colours in such a way that each subgraph H in Kn has at least two edges of the same colour. Equivalently, any edge-colouring of Kn with at least rb(n,H)=f(n,H)+1 colours contains a rainbow copy of H. Erdős, Simonovits and Sós have determined rb(n,Kk) for large enough n. Moreover, for k=3, they have shown that rb(n,K3)=n. In this paper we will determine the rainbow numbers rb(n,Kk) for all n⩾k⩾4, and the rainbow numbers rb(n,kK2) for all k⩾2 and n⩾3k+3.