FORBIDDEN RAINBOW SUBGRAPHS THAT FORCE LARGE HIGHLY CONNECTED MONOCHROMATIC SUBGRAPHS

摘要

We consider a forbidden rainbow structure condition which implies that an edge colored complete graph has an almost spanning monochromatic subgraph with high connectivity. Namely, we classify the connected graphs G that satisfy the following statement: If n ＞＞ m ＞＞ k are integers, then any rainbow G-free coloring of the edges of K_n using m colors contains a monochromatic k-connected subgraph of order at least n - f(G, k, m), where f does not depend on n.