Lassos: Pushing Tree Decompositions Forward Along Homomorphisms
Open Access
- 25 October 2026
- journal article
- research article
- Published by Springer Nature in Applied Categorical Structures
- Vol. 34 (6) , 63
Abstract
It is folklore that tree-width is monotone under taking subgraphs (i.e. injective graph homomorphisms) and contractions (certain kinds of surjective graph homomorphisms). However, although tree-width is obviously not monotone under any surjective graph homomorphism, it is not clear whether contractions are canonically the only class of surjections with respect to which it is monotone. Under the requirement that the decomposition shape must be preserved, we prove that this is indeed the case. Our results provide a framework for answering questions of this sort for many other kinds of combinatorial data structures (such as directed multigraphs, hypergraphs, Petri nets, circular port graphs, half-edge graphs, databases, simplicial sets etc.) for which natural analogues of tree decompositions can be defined. Furthermore and of independent interest, we prove these results by introducing the notion of a lasso , a generalization of contractions of graphs to arbitrary categories with pushouts of monomorphisms.Keywords
Funding Information
- DARPA ASKEM and Young Faculty Award programs (HR00112220038 and W911NF2110323)
- Deutsche Forschungsgemeinschaft (546892829)
This publication has 12 references indexed in Scilit:
- The structure of graphs not admitting a fixed immersionJournal of Combinatorial Theory, Series B, 2015
- Functorial data migrationInformation and Computation, 2012
- Graph Theory2010
- Rank-width and vertex-minorsJournal of Combinatorial Theory, Series B, 2005
- Handbook of Categorical Algebra1994
- Graph minors. X. Obstructions to tree-decompositionJournal of Combinatorial Theory, Series B, 1991
- The Robertson-Seymour theorems: a survey of applications1989
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- S-functions for graphsJournal of Geometry, 1976
- Δ-SETS I: HOMOTOPY THEORYThe Quarterly Journal of Mathematics, 1971