All minor-minimal apex obstructions with connectivity two

DOI10.37236/8382MaRDI QIDQ2223478zbMATH OpenOpenAlexWikidataFDO

Authors Adam S. Jobson, André E. Kézdy

Publication date 29 January 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

apex graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Abstract: A graph is an apex graph if it contains a vertex whose deletion leaves a planar graph. The family of apex graphs is minor-closed and so it is characterized by a finite list of minor-minimal non-members. The long-standing problem of determining this finite list of apex obstructions remains open. This paper determines the 133 minor-minimal, non-apex graphs that have connectivity two.

Review text

Summary: A graph is an apex graph if it contains a vertex whose deletion leaves a planar graph. The family of apex graphs is minor-closed and so it is characterized by a finite list of minor-minimal non-members. The long-standing problem of determining this finite list of apex obstructions remains open. This paper determines the 133 minor-minimal, non-apex graphs that have connectivity two.

Recommendations

• Six variations on a theme: almost planar graphs
• Minor obstructions for apex-pseudoforests
• The \(K_{n+5}\) and \(K_{3^2,1^n}\) families and obstructions to \(n\)-apex.
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Cliques, minors and apex graphs

Cites work

• A Characterization of Almost-Planar Graphs
• Excluded-minor characterization of apex-outerplanar graphs
• Graph minors. XX: Wagner's conjecture
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• scientific article; zbMATH DE number 5764786 (Why is no real title available?)
• Kuratowski chains
• Obtaining a planar graph by vertex deletion
• On almost-planar graphs
• Optimizing the graph minors weak structure theorem
• Petersen family minors
• Six variations on a theme: almost planar graphs

Cited in

(13)

• Six variations on a theme: almost planar graphs
• Face covers and the genus problem for apex graphs
• Minor obstructions for apex-pseudoforests
• Excluded-minor characterization of apex-outerplanar graphs
• Obstructions of connectivity two for embedding graphs into the torus
• The \(K_{n+5}\) and \(K_{3^2,1^n}\) families and obstructions to \(n\)-apex.
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Some excluded minors for the spindle surface
• Minor-obstructions for apex sub-unicyclic graphs
• Dips at small sizes for topological graph obstruction sets
• Delineating half-integrality of the Erdős-Pósa property for minors: the case of surfaces
• An overview of universal obstructions for graph parameters
• Minor-obstructions for apex sub-unicyclic graphs

This page was built for publication: All minor-minimal apex obstructions with connectivity two

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