Finding Minors in Graphs with a Given Path Structure

摘要

Given graphs G and H with V(H)V(G), suppose that we have a u,v-path Puv in G for each edge uv 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-4, and K-1,K- 1,K- 3 are contractible, but that graphs that are not 6-colorable and graphs that contain certain subdivisions of K-2,K- 3 are not contractible.