Invitation to torso parameters of annotated graphs
Abstract
An annotated graph is a pair (G,S), where G is a graph and S is a subset of vertices of G. We present a unified approach for definitions of annotated versions of classical graph parameters such as treewidth, pathwidth, treedepth, etc. A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph G and a subset S'⊆ V(G), we define torsoG(S') to be the graph with vertex set S' in which distinct vertices u,v∈ S' are adjacent if and only if there exists a u-v path in G whose internal vertices lie outside S'. Now let p be any graph parameter. For an annotated graph (G,S), we define the torso p of (G,S) by p(G,S) = min{p(torsoG(S')) | S ⊂ S' ⊂ V(G)}. For a minor-closed class of annotated graphs 𝒞, we discuss equivalent conditions for p(G,S) bounded for all (G,S)∈𝒞 in terms of annotated graphs excluded in 𝒞. In many cases, we collect known results from the literature. We include two new arguments for p being the $2$-treedepth and the feedback vertex number. Among other statements, we also include a variant of the Erdős-Pósa property for annotated cycles. We propose some new research directions.
Related
- Extremal Graphs with Prescribed Parameters for the Spectral Radius of Weighted Adjacency Matrices with Property P∗
- Weak k-metric dimension of Hamming graphs: rectangular products and near-maximum parameters
- Math for AI safety: an invitation for mathematicians
- Geometric Functional Inequalities for Markov Processes: An Invitation via the Langevin Diffusion
- An Invitation to Algebraic Methods in Quantum Theory
BibTeX
@misc{dumas2026invitation,
title = {{Invitation to torso parameters of annotated graphs}},
author = {Maël Dumas and Jędrzej Hodor and Tomasz Mazur and Piotr Micek and Clément Rambaud and Giannos Stamoulis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25905},
eprint = {2610.25905},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25905},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Invitation to torso parameters of annotated graphs
AU - Maël Dumas
AU - Jędrzej Hodor
AU - Tomasz Mazur
AU - Piotr Micek
AU - Clément Rambaud
AU - Giannos Stamoulis
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25905
UR - https://arxiv.org/abs/2610.25905
AB - An annotated graph is a pair (G,S), where G is a graph and S is a subset of vertices of G. We present a unified approach for definitions of annotated versions of classical graph parameters such as treewidth, pathwidth, treedepth, etc. A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph G and a subset S'⊆ V(G), we define torso_G(S') to be the graph with vertex set S' in which distinct vertices u,v∈ S' are adjacent if and only if there exists a u-v path in G whose internal vertices lie outside S'. Now let p be any graph parameter. For an annotated graph (G,S), we define the torso p of (G,S) by p(G,S) = min{p(torso_G(S')) | S ⊂ S' ⊂ V(G)}. For a minor-closed class of annotated graphs 𝒞, we discuss equivalent conditions for p(G,S) bounded for all (G,S)∈𝒞 in terms of annotated graphs excluded in 𝒞. In many cases, we collect known results from the literature. We include two new arguments for p being the $2$-treedepth and the feedback vertex number. Among other statements, we also include a variant of the Erdős-Pósa property for annotated cycles. We propose some new research directions.
ER -