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.

  • $\begingroup$ What is $\mathcal H$ here? $\endgroup$ – 1.. Sep 8 '19 at 15:52
  • $\begingroup$ $\mathcal{H}$ is any subgraph: math.stackexchange.com/questions/97226/h-minor-free-graph $\endgroup$ – user1246462 Sep 8 '19 at 16:54
  • 2
    $\begingroup$ 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). $\endgroup$ – Saeed Sep 9 '19 at 2:55

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)$.


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.