The Kelmans-Seymour conjecture. I: Special separations

DOI10.1016/J.JCTB.2019.11.008MaRDI QIDQ777488zbMATH 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/1511.05020

zbMATH Keywords

apex graphindependent pathsplanar graphseparationsubdivision

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of $K_5$. This conjecture was proved by Ma and Yu for graphs containing $K_4^{-}$, and an important step in their proof is to deal with a 5-separation in the graph with a planar side. In order to establish the Kelmans-Seymour conjecture for all graphs, we need to consider 5-separations and 6-separations with less restrictive structures. The goal of this paper is to deal with special 5-separations and 6-separations, including those with an apex side. Results will be used in subsequent papers to prove the Kelmans-Seymour conjecture.

Recommendations

• The Kelmans-Seymour conjecture. IV: A proof
• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• Subdivisions in apex graphs
• Independent paths and \(K_{5}\)-subdivisions

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
• Graphs containing topological H
• Independent paths and \(K_{5}\)-subdivisions
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)

Cited in

(11)

• Rooted topological minors on four vertices
• Subdivisions in apex graphs
• Graphs with \(3n-6\) edges not containing a subdivision of \(K_5\)
• Linking four vertices in graphs of large connectivity
• Independent paths and \(K_{5}\)-subdivisions
• Wheels in planar graphs and Hajós graphs
• 4‐Separations in Hajós graphs
• Chasing tripods to obtain a rooted subdivision
• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
• The Kelmans-Seymour conjecture. III: 3-vertices in \(K_4^-\)
• The Kelmans-Seymour conjecture. IV: A proof

This page was built for publication: The Kelmans-Seymour conjecture. I: Special separations

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