Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 303-319 |
Number of pages | 17 |
Journal | Discrete Mathematics |
Volume | 95 |
Issue number | 1-3 |
DOIs | |
State | Published - Dec 3 1991 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics