<p>A proper minor-closed family of graphs has bounded treewidth if and only if it's forbidden minors includes a planar graph. Thus, either the family contains all planar graphs or has bounded treewidth. In the former case the treewidth can be <span class="math-container">$\Omega(\sqrt{n})$</span> and in the latter case the treewidth is <span class="math-container">$O(1)$</span>.</p>

CC BY-SA 4.0
2019-09-08T18:38:55.177Z
2019-09-08T18:38:55.177Z
Chandra Chekuri
<p>What is the relationship between graphs which have <span class="math-container">$O(\log n)$</span> treewidth and <span class="math-container">$\mathcal{H}$</span>-minor-free graphs? Are graphs which have <span class="math-container">$O(\log n)$</span> treewidth <span class="math-container">$\mathcal{H}$</span>-minor-free? I know that graphs which are <span class="math-container">$\mathcal{H}$</span>-minor-free have treewidth <span class="math-container">$O(\sqrt{n})$</span> but I am concerned more with the relationship between <span class="math-container">$O(\log n)$</span> treewidth graphs and <span class="math-container">$\mathcal{H}$</span>-minor-free graphs.</p>

CC BY-SA 4.0
2019-09-08T15:52:02.277Z
What is $\mathcal H$ here?
Turbo
CC BY-SA 4.0
2019-09-08T16:54:23.390Z
$\mathcal{H}$ is any subgraph: https://math.stackexchange.com/questions/97226/h-minor-free-graph
user1246462
CC BY-SA 4.0
2019-09-09T02:55:32.137Z
Take a clique on log n vertices, attach a long path to it, it is not h minor free but its treewidth is O(log n).
Saeed
<graph-theory><graph-algorithms>
Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free
user1246462
# Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free

(Asked by: username_0 on 2019-09-08)

What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs which are $\mathcal{H}$-minor-free have treewidth $O(\sqrt{n})$ but I am concerned more with the relationship between $O(\log n)$ treewidth graphs and $\mathcal{H}$-minor-free graphs.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: What is $\mathcal H$ here?  
> **username_0**: $\mathcal{H}$ is any subgraph: https://math.stackexchange.com/questions/97226/h-minor-free-graph  
> **username_2**: Take a clique on log n vertices, attach a long path to it, it is not h minor free but its treewidth is O(log n).  

---

## 1 answers

### Answer by username_3 on 2019-09-08. Score: 8 | Accepted answer

A proper minor-closed family of graphs has bounded treewidth if and only if it's forbidden minors includes a planar graph. Thus, either the family contains all planar graphs or has bounded treewidth. In the former case the treewidth can be $\Omega(\sqrt{n})$ and in the latter case the treewidth is $O(1)$.


---

