Forbidden rainbow subgraphs that force large monochromatic or multicolored k-connected subgraphs

摘要

Let n, k, m be positive integers with n m k, and let C (respectively, be the set of connected (respectively, disconnected) graphs G such that there is a k-connected monochromatic subgraph of order at least n - f(G, k, m) in every rainbow G-free m-coloring of K-n, where f(G, k, m) does not depend on n. The set C was determined by Fujita and Magnant in a previous paper. In this paper, we give a complete characteriza- tion of and we show that G boolean OR H consists of precisely P-6, P-3 boolean OR P-4, K-2 boolean OR P-5, K-2 boolean OR 2P(3), 2K(2) boolean OR K-3, 2K(2) boolean OR P-4(+), 3K(2) boolean OR K-1,K-3 and their subgraphs.