Extremal results for rooted minor problems

✍ Scribed by Leif K Jørgensen; Ken-ichi Kawarabayashi

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 202 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20232

✦ Synopsis

Abstract

In this article, we consider the following problem. Given four distinct vertices v~1~,v~2~,v~3~,v~4~. How many edges guarantee the existence of seven connected disjoint subgraphs X~i~ for i = 1,…, 7 such that X~j~ contains v~j~ for j = 1, 2, 3, 4 and for j = 1, 2, 3, 4, X~j~ has a neighbor to each X~k~ with k = 5, 6, 7. This is the so called “rooted K~3, 4~‐minor problem.” There are only few known results on rooted minor problems, for example, [15,6]. In this article, we prove that a 4‐connected graph with n vertices and at least 5__n__ − 14 edges has a rooted K~3,4~‐minor. In the proof we use a lemma on graphs with 9 vertices, proved by computer search. We also consider the similar problems concerning rooted K~3,3~‐minor problem, and rooted K~3,2~‐minor problem. More precisely, the first theorem says that if G is 3‐connected and e(G) ≥ 4|G| − 9 then G has a rooted K~3,3~‐minor, and the second theorem says that if G is 2‐connected and e(G) ≥ 13/5|G| − 17/5 then G has a rooted K~3,2~‐minor. In the second case, the extremal function for the number of edges is best possible. These results are then used in the proof of our forthcoming articles 7, 8. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 191–207, 2007