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, K₄, and K_{1, 1, 3} are contractible, but that graphs that are not 6‐colorable and graphs that contain certain subdivisions of K_{2, 3} are not contractible.