# Tag Info

## Hot answers tagged treewidth

6

Answering my own question: the answer is "no". For each $k \ge 3$, Ding and Oporowski construct a graph $G_k$ on $2k$ vertices with treewidth $3$, such that in every optimal tree decomposition of $G_k$ there is a vertex which is in at least $2k-2$ bags (see Figure 1 in their paper). Ding, Guoli; Oporowski, Bogdan, Some results on tree decomposition of ...

4

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that is $n$-regular. We claim that the treewidth of $G^*$ is at least $n (n-1)/12$, which falsifies the conjecture. Proof: Suppose that the treewidth of $G^*$ is less ...

2

To clarify something:  does not use sunlet6, but C6. More specifically, the construction is as follows: Take G, subdivide every edge once, then make each old vertex additionally be part of its own new 6-cycle. In other words, if G has n vertices and m edges, G' has 6n + m vertices and 6n + 2m edges. The description you give isn't quite the same as this. ...

2

This recent paper studies the question in more depth: Clément Dallard, Martin Milanič, Kenny Štorgel. Treewidth versus clique number in graph classes with a forbidden structure. https://arxiv.org/abs/2006.06067

Only top voted, non community-wiki answers of a minimum length are eligible