A Structure Theorem for Strong Immersions |
| |
| Authors: | Zdeněk Dvo?ák Paul Wollan |
| |
| Institution: | 1. COMPUTER SCIENCE INSTITUTE OF CHARLES UNIVERSITY, PRAGUE, CZECH REPUBLICSupported the Center of Excellence – Inst. for Theor. Comp. Sci., Prague (project P202/12/G061 of Czech Science Foundation), and by project LH12095 (New combinatorial algorithms—decompositions, parameterization, efficient solutions) of Czech Ministry of Education;2. DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF ROME, “LA SAPIENZA”, ROME, ITALYSupported by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007‐2013)/ERC Grant Agreement no. 279558. |
| |
| Abstract: | A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices. |
| |
| Keywords: | graph minor graph immersion |
|
|
