2012/07/09 by Matt DeVos, DeVos, Matt, Jessica McDonald +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1207.2117
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 Kt-immersions; it is based on the Gomory-Hu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without Kt-immersions, where Kt denotes the bidirected complete digraph of order t.