{"id":"arxiv/2610.20407","url":"https://arxiv.org/abs/2610.20407","tags":["math.CO"],"score":0,"title":"Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers","domain":"math.CO","source":"arxiv","authors":["Xinheng Lin"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, let $\\mathrm{tw}(G)$, $\\mathrm{tree}\\text{-}α(G)$, and $\\mathrm{tree}\\text{-}χ(G)$ denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph $G$ satisfies $\\mathrm{tw}(G)+1\\leq\\mathrm{tree}\\text{-}α(G)\\mathrm{tree}\\text{-}χ(G)(1+\\lfloor\\log_2(\\mathrm{tree}\\text{-}α(G))\\rfloor)$. This improves the quadratic bound of Koutsoutis, Krause, Liu, Redzic, and Ueckerdt. For every pair of integers $n,k\\geq2$, we construct a graph $G$ with $\\mathrm{tree}\\text{-}α(G)=n$, $\\mathrm{tree}\\text{-}χ(G)=k$, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}