Tree decompositions whose trees are subgraphs: An application of Simon's factorization
2026-02-27 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors show that for any connected graph, you can create a tree-like structure called a tree decomposition where the tree itself is a part of the original graph. They prove that the complexity of this decomposition is limited by a property called the pathwidth of the graph, answering a question posed by Blanco and others in 2024. Their result contrasts with previous work that showed this isn’t possible if you measure complexity by treewidth instead. They use a mathematical tool called Simon's Factorization Theorem, and their proof is straightforward enough to help others learn this technique.
connected graphtree decompositiontreewidthpathwidthsubgraphSimon's Factorization Theoremfinite semigroupsgraph theorycombinatorics
Authors
Romain Bourneuf, Gwenaël Joret, Piotr Micek, Martin Milanič, Michał Pilipczuk
Abstract
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 theory and combinatorics in recent years. Our application is particularly simple and can serve as a good introduction to this technique.