Forbidding Kuratowski graphs as immersions

DOI10.1002/JGT.21790zbMATH Open1306.05232arXiv1207.5329OpenAlexW1916033929MaRDI QIDQ2940987FDOQ2940987

Authors: Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos 

Publication date: 21 January 2015

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: The immersion relation is a partial ordering relation on graphs that is weaker than the topological minor relation in the sense that if a graph $G$ contains a graph $H$ as a topological minor, then it also contains it as an immersion but not vice versa. Kuratowski graphs, namely $K_5$ and $K_{3,3}$, give a precise characterization of planar graphs when excluded as topological minors. In this note we give a structural characterization of the graphs that exclude Kuratowski graphs as immersions. We prove that they can be constructed by applying consecutive $i$-edge-sums, for $ileq3$, starting from graphs that are planar sub-cubic or of branch-width at most 10.

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

Recommendations

• The structure of graphs with no K3,3 immersion
• A note on immersion minors and planarity
• Excluding graphs as immersions in surface embedded graphs
• Planar graphs having no proper 2-immersions in the plane. I
• A weak immersion relation on graphs and its applications

zbMATH Keywords

tree-widthbranch-widthKuratowski graphsgraph immersions

Mathematics Subject Classification ID

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

Cites Work

• Graph minors. XIII: The disjoint paths problem
• Quickly excluding a planar graph
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Immersing small complete graphs
• A minimum degree condition forcing complete graph immersion
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. XVI: Excluding a non-planar graph
• Forbidden graphs for tree-depth
• Forbidden minors characterization of partial 3-trees
• On H‐immersions
• Outerplanar obstructions for a feedback vertex set
• Linkless embeddings of graphs in 3-space
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Optimizing the graph minors weak structure theorem
• Graphs with Branchwidth at Most Three
• Outerplanar obstructions for matroid pathwidth

Cited In (10)

• Complete graph immersions in dense graphs
• The structure of graphs with no K3,3 immersion
• The structure of graphs with no W4 immersion
• A note on immersion minors and planarity
• Excluding graphs as immersions in surface embedded graphs
• Planar graphs having no proper 2-immersions in the plane. I
• Planar graphs having no proper 2-immersions in the plane. III
• Characterizing graphs of small carving-width
• The structure of graphs not admitting a fixed immersion
• Edge degeneracy: algorithmic and structural results

This page was built for publication: Forbidding Kuratowski graphs as immersions

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