Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
In the authors' words
For a graph , let , , and denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph satisfies . This improves the quadratic bound of Koutsoutis, Krause, Liu, Redzic, and Ueckerdt. For every pair of integers , we construct a graph with , , and . Thus the upper bound is best possible up to a constant factor.
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages