Premium
Refining Tree‐Decompositions so That They Display the k ‐Blocks
Author(s) -
Albrechtsen Sandra
Publication year - 2025
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.23230
Subject(s) - refining (metallurgy) , mathematics , combinatorics , tree (set theory) , discrete mathematics , arithmetic , chemistry
ABSTRACT Carmesin and Gollin proved that every finite graph has a canonical tree‐decomposition( T , V )of adhesion less thankthat efficiently distinguishes every two distinctk‐profiles, and which has the further property that every separablek‐block is equal to the unique part of( T , V )in which it is contained. We give a shorter proof of this result by showing that such a tree‐decomposition can in fact be obtained from any canonical tight tree‐decomposition of adhesion less thank. For this, we decompose the parts of such a tree‐decomposition by further tree‐decompositions. As an application, we also obtain a generalization of Carmesin and Gollin's result to locally finite graphs.