The Kelmans-Seymour conjecture. IV: A proof

DOI10.1016/j.jctb.2019.12.002zbMath1443.05146arXiv1612.07189OpenAlexW2995620170MaRDI QIDQ777491

Xingxing Yu, Yan Wang, Dawei He

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/1612.07189

zbMATH Keywords

contractionconnectivityseparationindependent pathsdischarging\(K_5\)-subdivision

Mathematics Subject Classification ID

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

Related Items (4)

Linking four vertices in graphs of large connectivity ⋮ Wheels in planar graphs and Hajós graphs ⋮ 4‐Separations in Hajós graphs ⋮ Rooted topological minors on four vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent paths and \(K_{5}\)-subdivisions
• Some remarks on Hajós' conjecture
• The Kelmans-Seymour conjecture. I: Special separations
• The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
• The Kelmans-Seymour conjecture. III: 3-vertices in \(K_4^-\)
• A weaker version of Lovász' path removal conjecture
• Disjoint paths in graphs
• 2-linked graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• \(3n-5\) edges do force a subdivision of \(K_5\)
• Dirac's conjecture on \(K_ 5\)-subdivisions
• Disjoint paths in graphs. I: 3-planar graphs and basic obstructions
• Disjoint paths in graphs. II: A special case
• Topological minors in graphs of large girth
• Disjoint paths in graphs. III: Characterization
• On the conjecture of Hajos
• Graph connectivity after path removal
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• Subdivisions in apex graphs
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• Reducing Hajós' 4-coloring conjecture to 4-connected graphs
• Applications of Menger's graph theorem
• Homomorphism theorems for graphs
• Induced paths in 5-connected graphs
• Some Homeomorphism Properties of Graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• A Polynomial Solution to the Undirected Two Paths Problem
• Do 3n − 5 edges force a subdivision ofK5?
• K₅-Subdivisions in Graphs
• Cycles and Connectivity in Graphs
• How to Draw a Graph
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: The Kelmans-Seymour conjecture. IV: A proof