### Abstract

We define a quasi-order of the class of all finite hypergraphs, and prove it is a well-quasi-order. This has two corollaries of interest:•Wagner's conjecture, proved in a previous paper, states that for every infinite set of finite graphs, one of its members is a minor of another. The present result implies the same conclusion even if the vertices or edges of the graphs are labelled from a well-quasi-order and we require the minor relation to respect the labels.•Nash-Williams' "immersion" conjecture states that in any infinite set of finite graphs, one can be "immersed" in another; roughly, embedded such that the edges of the first graph are represented by edge-disjoint paths of the second. The present result implies this, in a strengthened form where we permit vertices to be labelled from a well-quasi-order and require the immersion to respect the labels.

Original language | English (US) |
---|---|

Pages (from-to) | 181-205 |

Number of pages | 25 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 100 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1 2010 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Graph minors
- Immersion
- Well-quasi-order

## Fingerprint Dive into the research topics of 'Graph minors XXIII. Nash-Williams' immersion conjecture'. Together they form a unique fingerprint.

## Cite this

*Journal of Combinatorial Theory. Series B*,

*100*(2), 181-205. https://doi.org/10.1016/j.jctb.2009.07.003