Extremal results for rooted minor problems |
| |
Authors: | Leif K Jørgensen Ken‐ichi Kawarabayashi |
| |
Institution: | 1. Department of Mathematical Sciences, Aalborg University, Fredrik Bajers VEJ 7E, Aalborg ?, DK‐9220, Denmark;2. Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, New Jersey, 08544, USA |
| |
Abstract: | In this article, we consider the following problem. Given four distinct vertices v1,v2,v3,v4. How many edges guarantee the existence of seven connected disjoint subgraphs Xi for i = 1,…, 7 such that Xj contains vj for j = 1, 2, 3, 4 and for j = 1, 2, 3, 4, Xj has a neighbor to each Xk with k = 5, 6, 7. This is the so called “rooted K3, 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 5n ? 14 edges has a rooted K3,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 K3,3‐minor problem, and rooted K3,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 K3,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 K3,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 |
| |
Keywords: | rooted minor problems extremal results |
|
|