Universal graphs without large bipartite subgraphs

Abstract Let 1 ≤ α ≤ β ≤ γ be cardinals, and letG γ ( K α ,   β)denote the class of all graphs on γ vertices having no subgraph isomorphic to K α,β . A graphG 0 ∈ G γ ( K α ,   β)is called universal if every G ∈ G γ ( K α ,   β)can be embedded into G o as a subgraph. We prove that, if α < ω ≤ γ and the General Continuum Hypothesis is assumed, thenG γ ( K α ,   β)has a universal element, if, and only if, (i) γ > ω or (ii) γ = ω , α = 1 and β ≤ 3. Using the Axiom of Constructibility, we also show that there does not exist a universal graph inG ω 1( K ω ,   ω 1) .