Extremal functions for rooted minors

✍ Scribed by Paul Wollan

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 208 KB
• Volume: 58
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20301

✦ Synopsis

Abstract

The graph G contains a graph H as a minor if there exist pairwise disjoint sets {S~i~ ⊆ V(G)|i = 1,…,|V(H)|} such that for every i, G[S~i~] is a connected subgraph and for every edge uv in H, there exists an edge of G with one end in S~u~ and the other end in S~v~. A rooted H minor in G is a minor where each S~i~ of the minor contains a predetermined x~i~ ∈ V(G). We prove that if the constant c is such that every graph on n vertices with cn edges contains an H minor, then every |V(H)|‐connected graph G with (9__c__ + 26,833|V(H)|)|V(G)| edges contains a rooted H minor for every choice of vertices {x~1~,…,x~|V(H)|~} ⊆ V(G). The proof methodology is sufficiently robust to find the exact extremal function for an infinite family of rooted bipartite minors previously studied by Jørgensen, Kawarabayashi, and Böhme and Mohar. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:159–178, 2008