Complete minors in complements of nonseparating planar graphs

DOI10.2140/INVOLVE.2023.16.505zbMATH Open1519.05058arXiv2204.10134OpenAlexW4385737212MaRDI QIDQ6132814FDOQ6132814

Authors: Leonard Fowler, Gregory Li, Andrei Pavelescu 

Publication date: 17 August 2023

Published in: Involve (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)