A structural duality for path-decompositions into parts of small radius

Autor:	Albrechtsen, Sandra, Diestel, Reinhard, Elm, Ann-Kathrin, Fluck, Eva, Jacobs, Raphael W., Knappe, Paul, Wollan, Paul
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics 05C10 (Primary) 05C75 05C12 05C62 05C83 (Secondary)
Druh dokumentu:	Working Paper
Popis:	Given an arbitrary class $\mathcal{H}$ of graphs, we investigate which graphs admit a decomposition modelled on a graph in $\mathcal{H}$ into parts of small radius. The $\mathcal{H}$-decompositions that we consider here generalise the notion of tree-decompositions. We identify obstructions to such $\mathcal{H}$-decompositions of small radial width, and we prove that these obstructions occur in every graph of sufficiently large radial $\mathcal{H}$-width for the classes $\mathcal{H}$ of paths, of cycles and of subdivided stars. Comment: 32 pages, 6 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2307.08497 Zobrazit plný text záznamu View this record from Arxiv