A note on forbidding clique immersions

Abstract

Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered 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 Gomory-Hu 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$.

References in corpus (1)

• Minimum degree condition forcing complete graph immersion