A note on forbidding clique immersions (Q396901)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on forbidding clique immersions |
scientific article |
Statements
A note on forbidding clique immersions (English)
0 references
14 August 2014
0 references
Summary: \textit{N. Robertson} and \textit{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\).
0 references