| Naslov: | Linear bounds on treewidth in terms of excluded planar minors |
|---|
| Avtorji: | ID Gollin, J. Pascal (Avtor)
ID Hendrey, Kevin (Avtor)
ID Oum, Sang-il (Avtor)
ID Reed, Bruce (Avtor) |
|---|
| Datoteke: |  RAZ_Gollin_J._Pascal_2025.pdf (613,98 KB)
MD5: 628F2E4245CA6B2FAD96A7E801EAF52C
 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i4p68
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | graph minor, treewidth, cycle packing |
|---|
| Datum objave: | 12.12.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | str. 1-23 |
|---|
| Številčenje: | Vol. 32, iss. 4, article no. P4.68 |
|---|
| PID: | 20.500.12556/RUP-22371  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1077-8926 |
|---|
| DOI: | 10.37236/12834 |
|---|
| COBISS.SI-ID: | 263444995 |
|---|
| Datum objave v RUP: | 05.01.2026 |
|---|
| Število ogledov: | 287 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
