An Extremal Problem on v-Partite Graphs

Let r, t, and v be positive integers with 2 ? t ? v. For a fixed graph G with t vertices, denote by Г (r, v, G) the class of all v-partite graphs H with vertex classes V_i, |V_i| = r (i =1, 2, ... , v) satisfying the following condition: For every t-subset {i₁, i₂, ... , i_t} of {1, 2, ... , v} there exists a subgraph of H isomorphic to G having exactly one vertex in each of the classes V_iτ, τ =1, 2, ... , t. Let cl(H) denote the clique number of H, i.e. the maximum order of a complete subgraph of H. We are interested in determining the value of the class parameter

$D(r,v,G)=\underset{H\in \Gamma (r,v,G)}{\min }cl(H)$

The main result is given the form of a Ramsey-type theorem (see Theorem 2.2). We shall show that for fixed r and G, D (r, v, G) tends to infinity when v tends to infinity if and only if χ(G) (the chromatic number of G) is greater than r. Some results concerning D(r, v, K_t), where K_t, is the complete graph on t vertices, are also given.