Maximum treewidth at a prescribed edge count
For an integer $e \ge 1$ let $$t(e) = \max\{\operatorname{tw}(G) : G \text{ is a finite simple graph with } |E(G)| = e\},$$ where $\operatorname{tw}(G)$ is the treewidth of $G$. Chen, Liu and Zhang computed $$t(e) = 1 \ (e \le 2), \quad 2 \ (3 \le e \le 5), \quad 3 \ (6 \le e \le 9), \quad 4 \ (10 \le e \le 14), \quad t(15) = 5.$$ Kneis, Mölle, Richter and Rossmanith proved that a graph with $m$ edges and $n$ vertices has pathwidth, and hence treewidth, at most $m/5.769 + O(\log n)$.
Problem. Determine $t(e)$ for all $e$: find a sharp upper bound on the treewidth of every finite simple graph in terms of its number of edges, together with graphs attaining it. Equivalently, determine for every positive integer $k$ the least number of edges of a graph of treewidth at least $k$.
Source: Chen, Liu and Zhang (2026), Appendix F, who ask for a sharp bound on treewidth in terms of the number of vertices or edges and compute t(e) for e ≤ 15 (Observation 1); stated in this form, as the determination of t(e), by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, extremal problems, tree decompositions, treewidth
References
@article{chen2026,
author = {Chen, Xingyu and Liu, Lin and Zhang, Ruiqi},
title = {On computing and the complexity of computing higher-order {$U$}-statistics, exactly},
journal = {Stat. Comput.},
volume = {36},
number = {5},
year = {2026},
pages = {Paper No. 223},
doi = {10.1007/s11222-026-10974-x},
eprint = {2508.12627},
archivePrefix = {arXiv},
}
@article{kneis2009,
author = {Kneis, Joachim and M{\"o}lle, Daniel and Richter, Stefan and Rossmanith, Peter},
title = {A bound on the pathwidth of sparse graphs with applications to exact algorithms},
journal = {SIAM J. Discrete Math.},
volume = {23},
number = {1},
year = {2009},
pages = {407--427},
doi = {10.1137/080715482},
}
@misc{aim-treewidth-edge-count,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Maximum treewidth at a prescribed edge count}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/551-treewidth-edge-count.md},
note = {Entry 551 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00396, "Maximum treewidth at a prescribed edge count", clopen.solutions.