Product structure extension of the Alon--Seymour--Thomas theorem

MaRDI QIDQ6507329arXivFDO

Authors Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, Michał T. Seweryn, David R. Wood

Abstract: A classical result of Alon, Seymour and Thomas [1990] states that every $n$-vertex graph excluding $K_t$ as a minor has treewidth less than $t^{3/2}sqrtn$. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth $t-1$, where each vertex is blown up by a complete graph of order $sqrttn$. We prove that the treewidth of $H$ can be reduced to $4$ while keeping blowups of size $O_t(sqrtn)$.

This page was built for publication: Product structure extension of the Alon--Seymour--Thomas theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507329)