Blow-up structure of graphs excluding a tree or an apex-tree as a minor
This work addresses structural graph theory problems for researchers in discrete mathematics, providing incremental improvements over recent theorems.
The paper tackles the problem of characterizing graphs that exclude specific minors, proving blow-up structure theorems for graphs excluding a tree or an apex-tree as a minor, with results including improved bounds on pathwidth and treewidth compared to prior work.
We prove blow-up structure theorems for graphs excluding a tree or an apex-tree as a minor. First, we show that for every $t$-vertex tree $T$ with $t\geq 3$ and radius $h$, and every graph $G$ excluding $T$ as a minor, there exists a graph $H$ with pathwidth at most $2h-1$ such that $G$ is contained in $H\boxtimes K_{t-2}$ as a subgraph. This improves on a recent theorem of DujmoviÄ, Hickingbotham, Joret, Micek, Morin, and Wood (2024), who proved the same result but with a larger bound on the order of the complete graph in the product. Second, we show that for every $t$-vertex tree $T$ with $t\geq 2$, radius $h$ and maximum degree $d$, and every graph $G$ excluding the apex-tree $T^+$ as a minor, where $T^+$ is the tree obtained by adding a universal vertex to $T$, there exists a graph $H$ with treewidth at most $4h-1$ such that $G$ is contained in $H\boxtimes K_{2(t-1)d}$. The bound on the treewidth of $H$ is best possible up to a factor $2$, and improves on a $2^{h+2}-4$ bound that follows from a recent result of DujmoviÄ, Hickingbotham, Hodor, Joret, La, Micek, Morin, Rambaud, and Wood (2024).