On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs

Abstract

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 $\mathrm{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 $\mathrm{tree}\text{-}\hat{I}\pm (G)$ and the tree-chromatic number $\mathrm{tree}\text{-}\ddot{I}‡(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 $\mathrm{tw}(G)+1\le \mathrm{tree}\text{-}\hat{I}\pm (G)\cdot \mathrm{tree}\text{-}\ddot{I}‡(G)$. We provide a negative answer for this question in a strong form: for every function $f:\mathbb{N}\to \mathbb{N}$, there exists a graph $G$ such that $\mathrm{tw}(G)>\mathrm{tree}\text{-}\hat{I}\pm (G)\cdot f(\mathrm{tree}\text{-}\ddot{I}‡(G))$. On the other hand, we complement this result with an upper bound, by showing that $\mathrm{tw}(G)+1\le \mathrm{tree}\text{-}\hat{I}\pm (G{)}^2\cdot \mathrm{tree}\text{-}\ddot{I}‡(G)$ for every graph $G$.