Highly connected coloured subgraphs via the regularity lemma

For integers n , r , s , k ∈ N , n ≥ k and r ≥ s , let m ( n , r , s , k ) be the largest (in order) k -connected component with at most s colours one can find in any r -colouring of the edges of the complete graph K n on n vertices. Bollobás asked for the determination of m ( n , r , s , k ) . bounds are obtained in the cases s = 1 , 2 and k = o ( n ) , which extend results of Liu, Morris and Prince. Our techniques use Szemerédi’s Regularity Lemma for many colours. ll also study a similar question for bipartite graphs.