2025/04/28 by Krause, Kilian, Redzic, Mirza, Ueckerdt, Torsten · 2 citations
#05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.19751
We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth \tw(G) of a graph G measures the largest number of vertices required in a bag of every tree decomposition of G. Similarly, the tree-independence number \tree-alpha(G) and the tree-chromatic number \tree-chi(G) measure the largest independence number, respectively the largest chromatic number, required in a bag of every tree decomposition of G. Recently, Dallard, Milanič, and Štorgel asked (JCTB, 2024) whether for all graphs G it holds that \tw(G)+1 ≤ \tree-alpha(G) ⋅ \tree-chi(G). We answer that question in the negative, providing examples G where \tw(G) is roughly 2⋅ \tree-alpha(G) ⋅ \tree-chi(G). For our approach we introduce H-subdivisions of G, which may be of independent interest, and give sharp bounds on the treewidth, tree-independence number, and tree-chromatic number of such graphs. Additionally, we give upper bounds on treewidth in terms of tree-independence number and tree-chromatic number that hold for all graphs G.