DeVos, Matt; McDonald, Jessica; Mohar, Bojan; Scheide, Diego A note on forbidding clique immersions. (English) Zbl 1295.05194 Electron. J. Comb. 20, No. 3, Research Paper P55, 5 p. (2013). Summary: N. Robertson and P. Seymour [J. Comb. Theory, Ser. B 100, No. 2, 181–205 (2010; Zbl 1216.05151)] 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\). Cited in 4 Documents MSC: 05C75 Structural characterization of families of graphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Citations:Zbl 1216.05151 PDFBibTeX XMLCite \textit{M. DeVos} et al., Electron. J. Comb. 20, No. 3, Research Paper P55, 5 p. (2013; Zbl 1295.05194) Full Text: arXiv