Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 6 min ago
Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics

Bounds on Treewidth via Excluding Disjoint Unions of Cycles

  • Meike Hatzel
  • Chun-Hung Liu
  • Bruce Reed
  • Sebastian Wiederrecht
Open at sourcePDFDOICite

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). The best bound known for an arbitrary planar H is O(|V(H)|9poly log|V(H)|). We show that if H is the disjoint union of cycles, then f(H) is O(|V(H)|log2 |V(H)|), which is a log|V(H)| factor away from being optimal.

Related

  1. An improved bound on the treewidth of planar graphs excluding a grid minor
    Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Induced packing treewidth II. Excluding a clique or a biclique
    Amir Nikabadi, Paweł Rzążewski
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Disjoint unions and fixed-parameter algorithms for chromatic villainy
    Jiang Jiang, Yuhan Jiang, Yiyang Li +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Complete characterization of disconnected one-point unions of cycles with local antimagic chromatic number 2
    Gee-Choon Lau, Wai Chee Shiu
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. New results on openly disjoint cycles in regular digraphs
    Bin Chen, Wenshen Wu, Meishaung Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{hatzel2026bounds,
  title = {{Bounds on Treewidth via Excluding Disjoint Unions of Cycles}},
  author = {Meike Hatzel and Chun-Hung Liu and Bruce Reed and Sebastian Wiederrecht},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = oct,
  doi = {10.37236/13735},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p8},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Bounds on Treewidth via Excluding Disjoint Unions of Cycles
AU  - Meike Hatzel
AU  - Chun-Hung Liu
AU  - Bruce Reed
AU  - Sebastian Wiederrecht
PY  - 2026
DA  - 2026/10/09
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/13735
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p8
AB  - 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). The best bound known for an arbitrary planar H is O(|V(H)|^9poly log|V(H)|). We show that if H is the disjoint union of cycles, then f(H) is O(|V(H)|log^2 |V(H)|), which is a log|V(H)| factor away from being optimal.
SN  - 1077-8926
ER  -