Show simple item record

dc.contributor.authorSong, Zixiaen_US
dc.date.accessioned2005-06-16T20:10:06Z
dc.date.available2005-06-16T20:10:06Z
dc.date.issued2004-07-08en_US
dc.identifier.urihttp://hdl.handle.net/1853/6425
dc.description.abstractIn 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.en_US
dc.format.extent549703 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectGraph minorsen_US
dc.subjectGraphen_US
dc.subjectHadwiger's conjectureen_US
dc.subject4-color theoremen_US
dc.subjectLinkageen_US
dc.subjectCockadeen_US
dc.subject.lcshGraph theoryen_US
dc.subject.lcshExtremal problems (Mathematics)en_US
dc.titleExtremal Functions for Contractions of Graphsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentAlgorithms, Combinatorics, and Optimizationen_US
dc.contributor.departmentMathematics
dc.description.advisorCommittee Chair: Robin Thomas ; Committee Members: Richard Duke ; Robert G. Parker ; Anurag Singh ; William T. Trotteren_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record