The excluded tree minor theorem revisited
type: Item
instance of: scholarly article
title: The excluded tree minor theorem revisited
author: Vida Dujmović
author: Robert Hickingbotham
author: Gwenaël Joret
author: Piotr Micek
author: Pat Morin
author: David R. Wood
published in: Combinatorics, Probability and Computing
publication date: 2024-11-05T00:00:00Z
review text: 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)].
reviewed by: V. Yegnanarayanan
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 7938713
zbMATH Keywords: structural graph theory
zbMATH Keywords: pathwidth
zbMATH Keywords: graph minors
MaRDI profile type: Publication
cites work: Quickly excluding a forest
cites work: Graph Minors I: A Short Proof of the Path-width Theorem
cites work: Graph Theory
cites work: Planar Graphs Have Bounded Queue-Number
cites work: Clustered colouring in minor-closed classes
cites work: Graph minors. I. Excluding a forest
DOI: 10.1017/S0963548323000275
description: scientific article; zbMATH DE number 7938713