Blow-up structure of graphs excluding a tree or an apex-tree as a minor
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.16615
curl -X POST /api/v1/records/arxiv/2603.16615/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.16615/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'