Finding Minors in Graphs with a Given Path Structure
Given graphs G and H with , suppose that we have a -path in G for each edge in H. There are obvious additional conditions that ensure that G contains H as a rooted subgraph, subdivision, or immersion; we seek conditions that ensure that G contains H as a rooted minor or minor. This naturally leads to studying sets of paths that form an H-immersion, with the additional property that paths that contain the same vertex must have a common endpoint. We say that H is contractible if, whenever G contains such an H-immersion, G must also contain a rooted H-minor. We show, for example, that forests, cycles, K4, and K1, 1, 3 are contractible, but that graphs that are not 6-colorable and graphs that contain certain subdivisions of K2, 3 are not contractible.
immersions graph minors schemes