Extremal Functions for Contractions of Graphs

Abstract

In this dissertation, a problem related to Hadwiger's conjecture has been studied. We first proved a conjecture of Jakobsen from 1983 which states that every simple graphs on $n$ vertices and at least (11n-35)/2 edges either has a minor isomorphic to K_8 with one edge deleted or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2} and/or K_7 by identifying cliques of size five. We then studied the extremal functions for complete minors. We proved that every simple graph on nge9 vertices and at least 7n-27 edges either has a minor, or is isomorphic to K_{2, 2, 2, 3, 3}, or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2, 2} by identifying cliques of size six. This result extends Mader's theorem on the extremal function for K_p minors, where ple7. We discussed the possibilities of extending our methods to K_{10} and K_{11} minors. We have also found the extremal function for K_7 plus a vertex minor.