pith. sign in

arxiv: 1302.3867 · v3 · pith:ZLMUVWVHnew · submitted 2013-02-15 · 🧮 math.CO

The structure of graphs not admitting a fixed immersion

classification 🧮 math.CO
keywords decompositionsdefinitionimmersionstructuretheoremtree-cutcutsgraph
0
0 comments X
read the original abstract

We present an easy structure theorem for graphs which do not admit an immersion of the complete graph. The theorem motivates the definition of a variation of tree decompositions based on edge cuts instead of vertex cuts which we call tree-cut decompositions. We give a definition for the width of tree-cut decompositions, and using this definition along with the structure theorem for excluded clique immersions, we prove that every graph either has bounded tree-cut width or admits an immersion of a large wall.

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.