A Structure Theorem for Strong Immersions

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10329890" target="_blank" >RIV/00216208:11320/16:10329890 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1002/jgt.21990" target="_blank" >http://dx.doi.org/10.1002/jgt.21990</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/jgt.21990" target="_blank" >10.1002/jgt.21990</a>

Result language
angličtina
Original language name
A Structure Theorem for Strong Immersions
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)