Subdivisions of complete graphs

K5-subdivision;Independent paths;Separation;Connectivity;Discharging;Contraction

Wang, Yan ; Yu, Xingxing Mathematics Peng, Richard Tetali, Prasad Thomas, Robin Warnke, Lutz ; Yu, Xingxing

University:Georgia Institute of Technology

Department:Mathematics

关键词: K5-subdivision;    Independent paths;    Separation;    Connectivity;    Discharging;    Contraction;   

Others  :  https://smartech.gatech.edu/bitstream/1853/58633/1/WANG-DISSERTATION-2017.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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.