Charles Explorer logo
🇬🇧

Immersion in four-edge-connected graphs

Publication at Faculty of Mathematics and Physics |
2016

Abstract

Fix g > 1. Every graph of large enough tree-width contains a g x g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g x g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion).

This result has a number of applications.