The excluded tree minor theorem revisited (Q6632794)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The excluded tree minor theorem revisited |
scientific article; zbMATH DE number 7938713
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The excluded tree minor theorem revisited |
scientific article; zbMATH DE number 7938713 |
Statements
The excluded tree minor theorem revisited (English)
0 references
5 November 2024
0 references
Motivated by the results of \textit{N. Robertson} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 35, 39--61 (1983; Zbl 0521.05062)], \textit{R. Diestel} [Comb. Probab. Comput. 4, No. 1, 27--30 (1995; Zbl 0829.05039)] and others, the authors in this article prove that for every tree \(T\) of radius \(h\), there is an integer \(c\) such that every \(T\)-minor-free graph is contained in the strong product of \(H\) and \(K_c\) for some graph \(H\) with pathwidth at most \(2h-1\). This is a qualitative strengthening of the result of Robertson and Seymour [loc. cit.] that for every tree \(T\), there is an integer \(c\) such that every \(T\) minor-free graph has pathwidth at most \(c\). They further obtain some more interesting results that further strengthen the results of \textit{S. Norin} et al. [Combinatorica 39, No. 6, 1387--1412 (2019; Zbl 1463.05518)].
0 references
structural graph theory
0 references
pathwidth
0 references
graph minors
0 references