{"id":"arxiv/2602.24270","url":"https://arxiv.org/abs/2602.24270","tags":["math.CO","cs.DM"],"score":0,"title":"Tree decompositions whose trees are subgraphs: An application of Simon's factorization","domain":"math.CO","source":"arxiv","authors":["Romain Bourneuf","Gwenaël Joret","Piotr Micek","Martin Milanič","Michał Pilipczuk"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-27","reactions":{}}