科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 (K) over right arrow (t)-immersions, where (K) over right arrow (t) denotes the complete digraph of order t.
- 出版日期2013-10-7
