Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers

For a graph $G$, let $\mathrm{t}\mathrm{w}(G)$, $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\alpha (G)$, and $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\chi (G)$ denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph $G$ satisfies $\mathrm{t}\mathrm{w}(G)+1\le \mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\alpha (G)\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\chi (G)(1+\lfloor {\log }_2(\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\alpha (G))\rfloor )$. This improves the quadratic bound of Koutsoutis, Krause, Liu, Redzic, and Ueckerdt. For every pair of integers $n,k\ge 2$, we construct a graph $G$ with $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\alpha (G)=n$, $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\text{-}\chi (G)=k$, and $\mathrm{t}\mathrm{w}(G)=\mathrm{\Omega }(nk{\log }_{2}n)$. Thus the upper bound is best possible up to a constant factor.