Forbidding Kuratowski graphs as immersions

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

Research output: Contribution to journalArticlepeer-review


Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K5 and K3,3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for i ∈ {1, 2, 3}. We also use this result to give a structural characterization of graphs that exclude K3,3 as an immersion.

Original languageEnglish (US)
Pages (from-to)43-60
Number of pages18
JournalJournal of Graph Theory
Issue number1
StatePublished - Jan 1 2015


  • Branch-width
  • Graph immersions
  • Kuratowski graphs
  • Tree-width

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'Forbidding Kuratowski graphs as immersions'. Together they form a unique fingerprint.

Cite this