Extremal results for graph minors

  • Jørgensen, Leif Kjær (Project Participant)

Project Details


For a given graph H with vertices x_1, ... , x_p, a graph G has H as a minor if G contains disjoint connected subgraphs V_1, ... , V_p, such that if there is an edge between x_i and x_j then there is an edge between V_i and V_j. The minor is rooted at {v_1, ... , v_r} if v_i belongs to V_i, for i=1, ... , r. We consider results of the following type: every k-connected graph G with n vertices and at least f(n) edges contains H as a minor (rooted at X, for any subset X of k vertices in G). In particular, we prove that every 4-connected graph with n vertices and at least 5n-14 edges has the complete bipartite graph K_4,3 as a minor rooted at any set of four vertices. Cooperation with Ken-ichi Kawarabayashi, Tohoku University.
Effective start/end date31/12/200731/12/2007