The excluded tree minor theorem revisited (Q6632794)

From MaRDI portal





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
    0 references
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers