
Matt DeVos

Jessica McDonald

Bojan Mohar

Diego Scheide
Keywords:
Graph theory, Immersion
Abstract
Robertson and Seymour proved that the relation of graph immersion is wellquasiordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there is a very short proof of the corresponding rough structure theorem for graphs without $K_t$immersions; it is based on the GomoryHu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without $\vec{K}_t$immersions, where $\vec{K}_t$ denotes the bidirected complete digraph of order $t$.