### Abstract

A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v1,...,vn} in such a way that for each j, there are at most k edges uv such that u∈{v1,...,vj-1} and v∈{vj,...,vn}.We prove that for every set S of tournaments, the following are equivalent: •there is a digraph H such that H cannot be strongly immersed in any member of S,•there exists k such that every member of S has cutwidth at most k,•there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles. This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament.

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

Pages (from-to) | 93-101 |

Number of pages | 9 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 102 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2012 |

### All Science Journal Classification (ASJC) codes

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

### Keywords

- Cutwidth
- Immersion
- Tournament

## Fingerprint Dive into the research topics of 'Tournament immersion and cutwidth'. Together they form a unique fingerprint.

## Cite this

*Journal of Combinatorial Theory. Series B*,

*102*(1), 93-101. https://doi.org/10.1016/j.jctb.2011.05.001