An Improved Quasi‐Isometry Between Graphs of Bounded Cliquewidth and Graphs of Bounded Treewidth
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.
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}
}
EUVIMED