2025/05/14 by Distel, Marc · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2505.09834
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 k admit a partition with `local, but dense' parts whose quotient has treewidth k-1. Specifically, each part is contained within the closed neighbourhood of some vertex. We use this to construct a 3-quasi-isometry between graphs of cliquewidth k and graphs of treewidth k-1. 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.