2
$\begingroup$

What is the maximum treewidth of a graph with $m$ edges? In other words, what is the correct growth for the following function?

$\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has $m$ edges}\}$.

Clearly $\alpha(m) = \Omega(\sqrt{m})$, which is attained by cliques with $\Omega(\sqrt{m})$ vertices and by by $\Omega(\sqrt{m})\times \Omega(\sqrt{m})$ grids.

Is this also the maximum?

$\endgroup$
  • 7
    $\begingroup$ cubic expanders have linear treewidth. $\endgroup$ – PsySp Sep 12 '17 at 12:38
  • $\begingroup$ @PsySp Could you please post this as an answer with a reference to the fact that expanders have linear treewidth? $\endgroup$ – Springberg Sep 12 '17 at 22:31
7
$\begingroup$

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in:

Martin Grohe, Dániel Marx: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009)

Basically, they prove something much stronger: large vertex expansion is the only reason on why the treewidth can be as much as linear (in the number of vertices, but bounded degree graphs have linear number of edges).

$\endgroup$
4
$\begingroup$

The best known upper bound of the treewidth in terms of the number of edges of a graph is as follows: the pathwidth (and therefore also the treewidth) of any graph on $n$ vertices and $m$ edges is at most $13 m / 75 + o(n)$.

Alexander D. Scott and Gregory B. Sorkin. Linear-programming design and analysis of fast algorithms for Max 2-CSP, Discrete Optimization 4 (2007), no. 3-4, 260-287. https://arxiv.org/abs/cs/0604080

Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith, A bound on the pathwidth of sparse graphs with applications to exact algorithms, SIAM Journal on Discrete Mathematics 23 (2009), no. 1, 407-427.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.