Portal de Periódicos da CAPES

Excluding infinite minors

1991; Elsevier BV; Volume: 95; Issue: 1-3 Linguagem: Inglês

10.1016/0012-365x(91)90343-z

1872-681X

Neil Robertson, Paul Seymour, Robin Thomas,

Limits and Structures in Graph Theory

Let κ be an infinite cardinal, and let H be either a complete graph with κ vertices, or a tree in which every vertex has valency κ . What can we say about graphs G which (i) have no minor isomorphic to H , or (ii) contain no subgraph which is a subdivision of H ? These four questions are answered for each infinite cardinal κ . In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.