Topological minors in bipartite graphs

Abstract

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn−(2(m−s)+n−t+ 1) edges for this topological Turan type problem.