Tree decompositions whose trees are subgraphs: An application of Simon's factorization
We show that every connected graph $G$ has a tree decomposition indexed by a tree $T$ such that $T$ is a subgraph of $G$ and the width of the tree decomposition is bounded from above by a function of the pathwidth of $G$. This answers a question of Blanco, Cook, Hatzel, Hilaire, Illingworth, and McCarty (2024), who proved that it is not possible to have such a tree decomposition whose width is bounded by a function of the treewidth of $G$. The proof relies on Simon's Factorization Theorem for finite semigroups, a tool that has already been applied successfully in various areas of graph…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.24270
curl -X POST /api/v1/records/arxiv/2602.24270/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.24270/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'