The Kelmans-Seymour conjecture. III: 3-vertices in K₄^-

DOI10.1016/J.JCTB.2019.11.006MaRDI QIDQ777490zbMATH OpenOpenAlexFDO

Authors Da-Wei He, Yan Wang, Xingxing Yu

Publication date 7 July 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05747

zbMATH Keywords

independent pathsnonseparating pathplanar graphsubdivision of graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G$ be a 5-connected nonplanar graph and let $x_1,x_2,y_1,y_{2}inV(G)$ be distinct, such that $G[x_1,x_2,y_1,y_2]cong{K}_4^{-}$ and $y_1{y}_{2}otinE(G)$. We show that one of the following holds: $G-x_1$ contains $K_4^{-}$, or $G$ contains a $K_4^{-}$ in which $x_1$ is of degree 2, or $G$ contains a $T{K}_5$ in which $x_1$ is not a branch vertex, or $x_2,y_1,y_2$ may be chosen so that for any distinct $z_0,z_{1}inN(x_1)-x_2,y_1,y_2$, $G-x_{1}v:votin{z}_0,z_1,x_2,y_1,y_2$ contains $T{K}_5$. This result will be used to prove the Kelmans-Seymour conjecture.

Recommendations

• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• Subdivisions in apex graphs
• The Kelmans-Seymour conjecture. I: Special separations
• The Kelmans-Seymour conjecture. IV: A proof

Cites work

• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Applications of Menger's graph theorem
• Contractible edges and triangles in k-connected graphs
• Cycles and Connectivity in Graphs
• Disjoint paths in graphs
• Graph minors. IX: Disjoint crossed paths
• Independent paths and \(K_{5}\)-subdivisions
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• The Kelmans-Seymour conjecture. I: Special separations
• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)

Cited in

(10)

• The existence of \(\text{KS}_3(v;2,4)\)
• Rooted topological minors on four vertices
• Subdivisions in apex graphs
• Linking four vertices in graphs of large connectivity
• Wheels in planar graphs and Hajós graphs
• 4‐Separations in Hajós graphs
• Chasing tripods to obtain a rooted subdivision
• The dominating 4-colour theorem
• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
• The Kelmans-Seymour conjecture. IV: A proof

This page was built for publication: The Kelmans-Seymour conjecture. III: 3-vertices in \(K_4^-\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777490)