Fix g > 1. Every graph of large enough tree-width contains a g× g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g× 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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Graph immersion
- Grid minors