Kuratowski chains

DOI10.1006/JCTB.1995.1030MaRDI QIDQ1898717zbMATH OpenOpenAlexFDO

Authors Neil Robertson, Robin Thomas, Paul Seymour

Publication date 20 September 1995

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

Full work available at URL https://doi.org/10.1006/jctb.1995.1030

zbMATH Keywords

embedding conjectureKuratowski chainslinkless embeddingseparationsubdivisions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Review text

If \(H\) and \(H'\) are subgraphs of \(G\), both isomorphic to subdivisions of \(K_5\) or \(K_{3,3}\), then the following are equivalent: (1) There is a sequence \(H= H_1, H_2,\dots, H_k= H'\) of subgraphs of \(G\), each isomorphic to a subdivision of \(K_5\) or \(K_{3,3}\) and ``slightly different from its predecessor; (2) \(H\) and \(H'\) are not ``separated in \(G\) by a vertex separation of order \(\leq 3\). This result is eventually used by the three authors in their proof of Sachs' embedding conjecture [J. Comb. Theory, Ser. B 64, No. 2, 185-227 (1995; Zbl 0832.05032)].

Recommendations

• Independent paths and \(K_{5}\)-subdivisions
• A strengthening of the Kuratowski planarity criterion for 3-connected graphs
• A refinement of Kuratowski's theorem
• The Kelmans-Seymour conjecture. IV: A proof
• scientific article; zbMATH DE number 3887721

Cited in

(11)

• A polynomial-time algorithm to find a linkless embedding of a graph
• Another Bruen chain
• All minor-minimal apex obstructions with connectivity two
• Knots and links in spatial graphs: a survey
• Elimination of local bridges
• Linkless and flat embeddings in 3-space
• On Linked Spatial Representations
• Linkless embeddings of graphs in 3-space
• A refinement of Kuratowski's theorem
• Some recent progress and applications in graph minor theory
• Path transferability of graphs

This page was built for publication: Kuratowski chains

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