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

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