PreprintarXiv licencearXiv
Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
Abstract
For a graph G, let tw(G), tree−α(G), and tree−χ(G) denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph G satisfies tw(G)+1≤tree−α(G)tree−χ(G)(1+⌊log2(tree−α(G))⌋). This improves the quadratic bound of Koutsoutis, Krause, Liu, Redzic, and Ueckerdt. For every pair of integers n,k≥2, we construct a graph G with tree−α(G)=n, tree−χ(G)=k, and tw(G)=Ω(nklog2 n). Thus the upper bound is best possible up to a constant factor.
Related
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
- Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
BibTeX
@misc{lin2026treewidth,
title = {{Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers}},
author = {Xinheng Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20407},
eprint = {2610.20407},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20407},
}
RIS
TY - UNPB
TI - Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
AU - Xinheng Lin
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20407
UR - https://arxiv.org/abs/2610.20407
AB - For a graph G, let tw(G), tree−α(G), and tree−χ(G) denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph G satisfies tw(G)+1≤tree−α(G)tree−χ(G)(1+⌊log_2(tree−α(G))⌋). This improves the quadratic bound of Koutsoutis, Krause, Liu, Redzic, and Ueckerdt. For every pair of integers n,k≥2, we construct a graph G with tree−α(G)=n, tree−χ(G)=k, and tw(G)=Ω(nklog_2 n). Thus the upper bound is best possible up to a constant factor.
ER -