Complete minors in complements of nonseparating planar graphs

DOI10.2140/INVOLVE.2023.16.505MaRDI QIDQ6132814zbMATH OpenOpenAlexFDO

Authors Leonard Fowler, Gregory Li, Andrei Pavelescu

Publication date 17 August 2023

Published in Involve (Search for Journal in Brave)

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

zbMATH Keywords

graph minorsintrinsically knottedHadwiger numbernonseparating planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Relations of low-dimensional topology with graph theory (57M15)

Abstract: We prove that the complement of any non-separating planar graph of order $2n-3$ contains a $K_n$ minor, and argue that the order $2n-3$ is lowest possible with this property. To illustrate the necessity of the non-separating hypothesis, we give an example of a planar graph of order 11 whose complement does not contain a $K_7$ minor. We argue that the complements of planar graphs of order 11 are intrinsically knotted. We compute the Hadwiger numbers of complements of wheel graphs.

Recommendations

• Complete graph minors and the graph minor structure theorem
• scientific article; zbMATH DE number 3258070
• Complete minors in \(K_{s,s}\)-free graphs
• Complete Minors in Graphs Without Sparse Cuts
• Clique minors in graphs and their complements
• Minimal non-1-planar graphs
• Complete minors, independent sets, and chordal graphs
• Minimal Split Completions of Graphs
• scientific article; zbMATH DE number 1495914

Cites work

• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• An algorithm for detecting intrinsically knotted graphs
• Every planar graph with nine points has a nonplanar complement
• Graph minors. XX: Wagner's conjecture
• Intrinsically knotted graphs
• Knots and links in spatial graphs
• Many, many more intrinsically knotted graphs
• Non-separating planar graphs
• Practical graph isomorphism. II.
• Realization of knots and links in a spatial graph
• The Colin de Verdière number and sphere representations of a graph
• The Non-Biplanar Character of the Complete 9-Graph

Cited in

(4)

• \(K_7\)-minors in optimal 1-planar graphs
• Non-separating planar graphs
• Complete Minors in Graphs Without Sparse Cuts
• Constructions stemming from nonseparating planar graphs and their Colin de Verdière invariant

This page was built for publication: Complete minors in complements of nonseparating planar graphs

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