Special TK5 in graphs containing K4-

Given a graph K, TK is used to denote a subdivision of K, which is a graph obtained from K by substituting some edges for paths. The well-known Kelmans-Seymour conjecture states that every nonplanar 5-connected graph contains TK5 . Ma and Yu proved the conjecture for graphs containing K4-. In this dissertation, we strengthen their result in two ways. The results will be useful for completely resolving the Kelmans-Seymour conjecture. Let G be a 5-connected nonplanar graph and let x1, x2, y1, y2 in V(G) be distinct, such that G[{x1, x2, y1, y2}] is isomorphic to K4- and y1y2 is not in E(G). We show that one of the following holds: G - y2 contains K4-, or G contains a TK5 in which y2 is not a branch vertex, or G has a special 5-separation, or for any distinct w1, w2, w3 in N(y2) - {x1, x2}, G - {y2v : v not in {x1, x2, w1, w2, w3}} contains TK5. We show that one of the following holds: G - x1 contains K4-, or G contains a TK5 in which x1 is not a branch vertex, or G contains a K4- in which x1 is of degree 2, or {x2, y1, y2} may be chosen so that for any distinct z0, z1 in N(x1) - {x2, y1, y2}, G - {x1v : v not in {z0, z1, x2, y1, y2}} contains TK5.

Level thesis:degree_level

Doctoral

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Georgia Institute of Technology

Year dc:date.issued

2017

Author dc:creator

• He, Dawei

Advisor dc:contributor.advisor

• Yu, Xingxing

Committee members dc:contributor.committeemember

• Thomas, Robin
• Trotter, William
• Blekhermann, Greg
• Li, Geoffrey Ye

• Kelmans-Seymour conjecture
• Subdivision of K5
• K4-
• Branch vertex

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1853/58301

OAI identifier oai:identifier

oai:repository.gatech.edu:1853/58301