Linear bounds on treewidth in terms of excluded planar minors ...
arXiv, 2024
report
Zugriff:
One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$. A lower bound for ${f(H)}$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth ${Ω(k\log k)}$ which does not contain $k$ vertex-disjoint cycles, from which it follows that ${f(H) = Ω(k\log k)}$. In particular, if ${f(H)}$ is linear in ${\lvert{V(H)}\rvert}$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$-vertex graphs from the class contain at most ${O(n/\log(n))}$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$-vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$, and improve this to ${f(H) \leq n + O(\sqrt{n})}$ ... : 18 pages ...
Titel: |
Linear bounds on treewidth in terms of excluded planar minors ...
|
---|---|
Autor/in / Beteiligte Person: | Gollin, J. Pascal ; Hendrey, Kevin ; Oum, Sang-il ; Reed, Bruce |
Link: | |
Veröffentlichung: | arXiv, 2024 |
Medientyp: | report |
DOI: | 10.48550/arxiv.2402.17255 |
Schlagwort: |
|
Sonstiges: |
|