Invitation to torso parameters of annotated graphs
En palabras de los autores
An annotated graph is a pair , where is a graph and is a subset of vertices of . 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 and a subset , we define to be the graph with vertex set in which distinct vertices are adjacent if and only if there exists a - path in whose internal vertices lie outside . Now let be any graph parameter. For an annotated graph , we define the torso of by \[p(G,S) = \min\{p(torso_G(S')) \mid S \subset S' \subset V(G)\}.\] For a minor-closed class of annotated graphs , we discuss equivalent conditions for bounded for all in terms of annotated graphs excluded in . In many cases, we collect known results from the literature. We include two new arguments for being the -treedepth and the feedback vertex number. Among other statements, we also include a variant of the Erd\H{o}s-P\'osa property for annotated cycles. We propose some new research directions.
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 27 pages, 4 figures