pith. sign in

arxiv: 1207.2117 · v1 · pith:7HBNQNLOnew · submitted 2012-07-09 · 🧮 math.CO

A note on forbidding clique immersions

classification 🧮 math.CO
keywords immersionsprooftheoremgraphgraphsroughstructurewithout
0
0 comments X
read the original 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.