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

Abstract

For a graph $G$, let $\mathrm{tw}(G)$, $\mathrm{tree}\text{-}\alpha (G)$, and $\mathrm{tree}\text{-}\chi (G)$ denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph $G$ satisfies $\mathrm{tw}(G)+1\le \mathrm{tree}\text{-}\alpha (G)\mathrm{tree}\text{-}\chi (G)(1+\lfloor {\log }_2(\mathrm{tree}\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{tree}\text{-}\alpha (G)=n$, $\mathrm{tree}\text{-}\chi (G)=k$, and $\mathrm{tw}(G)=\Omega (nk{\log }_{2}n)$. Thus the upper bound is best possible up to a constant factor.

arXiv comment8 pages