1. Linear bounds on treewidth in terms of excluded planar minorsJ. Pascal Gollin, Kevin Hendrey, Sang-il Oum, Bruce Reed, 2025, original scientific article Abstract: 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 $\Omega(k\log k)$ which does not contain $k$ vertex-disjoint cycles, from which it follows that $f(H) = \Omega(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 $\lvert V(H) \rvert$ 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)$≤$n$+O(√$n$) when $r$=2. In particular this bound is linear when $r$=O(√$n$/logn). We present a linear bound for $f(H)$ when $H$ is a subdivision of an $r$-edge planar graph for any constant~$r$. We also improve the best known bounds for $f(H)$ when $H$ is the wheel graph or the 4×4 grid, obtaining a bound of 160 for the latter.
Keywords: graph minor, treewidth, cycle packing
Published in RUP: 05.01.2026; Views: 1472; Downloads: 3
 Full text (613,98 KB)
This document has more files! More... |
2. On relationships between treewidth, clique number, tree-independence number, and induced minors : master’s thesisÐorđe Vasić, 2025, master's thesis Keywords: treewidth, clique number, tree-independence number, induced minor, hered itary graph class, bipartite chain graph
Published in RUP: 11.09.2025; Views: 1856; Downloads: 40
Full text (839,36 KB) |
3. |
4. |
5. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doctoral dissertation Keywords: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Published in RUP: 09.11.2017; Views: 7071; Downloads: 86
Full text (970,91 KB) |
