Forbidding Kuratowski Graphs as Immersions |
| |
| Authors: | Archontia C Giannopoulou Marcin Kamiński Dimitrios M Thilikos |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICS, NATIONAL AND KAPODISTRIAN UNIVERSITY OF ATHENS, PANEPISTIMIOUPOLIS, GR‐15784 ATHENS, GREECE AND DEPARTMENT OF INFORMATICS, UNIVERSITY OF BERGEN, BERGEN, NORWAY;2. DEPARTMENT OF MATHEMATICS, COMPUTER SCIENCE, AND MECHANICS, UNIWERSYTET WARSZAWSKI, WARSAW, POLAND;3. DEPARTMENT OF MATHEMATICS, NATIONAL AND KAPODISTRIAN UNIVERSITY OF ATHENS, PANEPISTIMIOUPOLIS, GR‐15784 ATHENS, GREECE AND ALGCO PROJECT TEAM, CNRS, LIRMM, FRANCE |
| |
| Abstract: | 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  . We also use this result to give a structural characterization of graphs that exclude K3, 3 as an immersion. |
| |
| Keywords: | graph immersions Kuratowski graphs tree‐width branch‐width |
|
|
