Back to search

Georgia Institute of Technology

Subdivisions of complete graphs

Abstract

dc:description.abstract

A subdivision of a graph G, also known as a topological G and denoted by TG, is a graph obtained from G by replacing certain edges of G with internally vertex-disjoint paths. This dissertation studies a problem in structural graph theory regarding subdivisions of a complete graph in graphs. In this dissertation, we focus on TK_5, or subdivisions of K_5. A well known theorem of Kuratowski in 1932 states that a graph is planar if, and only if, it does not contain a subdivision of K_5 or K_{3,3}. Wagner proved in 1937 that if a graph other than K_5 does not contain any subdivision of K_{3,3} then it is planar or it admits a cut of size at most 2. Kelmans and, independently, Seymour conjectured in the 1970s that if a graph does not contain any subdivision of K_5 then it is planar or it admits a cut of size at most 4. In this dissertation, we give a proof of the Kelmans-Seymour conjecture.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Yan
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Peng, Richard
  • Tetali, Prasad
  • Thomas, Robin
  • Warnke, Lutz

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Wang, Yan. Subdivisions of complete graphs. Doctoral thesis, Georgia Institute of Technology, 2017. http://hdl.handle.net/1853/58633