Back to search

Georgia Institute of Technology

Extremal Functions for Contractions of Graphs

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Algorithms, Combinatorics, and Optimization
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Song, Zixia
Advisor dc:contributor.advisor
  • Thomas, Robin
Committee members dc:contributor.committeemember
  • Richard Duke
  • Robert G. Parker
  • Anurag Singh
  • William T. Trotter

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/6425

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Song, Zixia. Extremal Functions for Contractions of Graphs. Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/6425