EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

An Improved Quasi‐Isometry Between Graphs of Bounded Cliquewidth and Graphs of Bounded Treewidth

Marc Distel

Journal of Graph Theory · 2026-08 · 112 (4) · 409-420

DOI: 10.1002/jgt.70037 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 08.04.2026. Verfasst von Marc Distel. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Australian Government.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Cliquewidth is a dense analogue of treewidth. It can be deduced from recent results by Hickingbotham [arXiv:2501.10840] and Nguyen, Scott, and Seymour [arXiv:2501.09839] that graphs of bounded cliquewidth are quasi‐isometric to graphs of bounded treewidth. We improve on this by showing that graphs of cliquewidth admit a partition with ‘local, but dense’ parts whose quotient has treewidth . Specifically, each part is contained within a closed neighbourhood of some vertex. We use this to construct a 3‐quasi‐isometry between graphs of cliquewidth and graphs of treewidth . This is an improvement in both the quasi‐isometry parameter and the treewidth. We also show that the bound on the treewidth is tight up to an additive constant.

Förderung

  • Australian Government

Zitieren

APA

Distel, M. (2026). An Improved Quasi‐Isometry Between Graphs of Bounded Cliquewidth and Graphs of Bounded Treewidth. Journal of Graph Theory, 112(4), 409-420. https://doi.org/10.1002/jgt.70037

Vancouver

Distel M. An Improved Quasi‐Isometry Between Graphs of Bounded Cliquewidth and Graphs of Bounded Treewidth. Journal of Graph Theory. 2026;112(4):409-420. doi:10.1002/jgt.70037

BibTeX
@article{Distel2026,
  author = {Distel, Marc},
  title = {An Improved Quasi‐Isometry Between Graphs of Bounded Cliquewidth and Graphs of Bounded Treewidth},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {112},
  number = {4},
  pages = {409--420},
  doi = {10.1002/jgt.70037}
}
Kostenlos starten →