pipette
ESEspañol

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

Xinheng Lin

Preprint

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