Show simple item record

dc.contributor.advisorYu, Xingxing
dc.contributor.authorHe, Dawei
dc.date.accessioned2017-06-07T17:47:36Z
dc.date.available2017-06-07T17:47:36Z
dc.date.created2017-05
dc.date.issued2017-04-05
dc.date.submittedMay 2017
dc.identifier.urihttp://hdl.handle.net/1853/58301
dc.description.abstractGiven 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.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectKelmans-Seymour conjecture
dc.subjectSubdivision of K5
dc.subjectK4-
dc.subjectBranch vertex
dc.titleSpecial TK5 in graphs containing K4-
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentMathematics
thesis.degree.levelDoctoral
dc.contributor.committeeMemberThomas, Robin
dc.contributor.committeeMemberTrotter, William
dc.contributor.committeeMemberBlekhermann, Greg
dc.contributor.committeeMemberLi, Geoffrey Ye
dc.date.updated2017-06-07T17:47:36Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record